Dang_Quan_10_Tin

LIGHT

Apr 16th, 2022
848
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #define task "LIGHT"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <algorithm>
  7. using namespace std;
  8. using ll = long long;
  9. using ld = long double;
  10.  
  11. constexpr int N = 1e5 + 2;
  12. constexpr int block = 320;
  13. constexpr int Inf = 1e9 + 7;
  14.  
  15. int n, m, q;
  16. vector<pair<int, int>> adj[N];
  17. int c[N], cnt[N][2], ans(0), cv[N];
  18.  
  19. // 1 : xenh
  20. // 0 : do
  21.  
  22. void Read()
  23. {
  24.     cin >> n >> m >> q;
  25.  
  26.     for (int i = 1; i <= m; ++i)
  27.     {
  28.         int u, v;
  29.         cin >> u >> v >> c[i];
  30.  
  31.         adj[u].emplace_back(v, i);
  32.         adj[v].emplace_back(u, i);
  33.  
  34.         ++cnt[u][c[i]];
  35.         ++cnt[v][c[i]];
  36.  
  37.         ans += c[i];
  38.     }
  39. }
  40.  
  41. void Solve()
  42. {
  43.     for (int i = 1; i <= n; ++i)
  44.         sort(adj[i].begin(), adj[i].end(), [&](const pair<int, int> &x, const pair<int, int> &y)
  45.              { return adj[x.first].size() > adj[y.first].size(); });
  46.  
  47.     while (q--)
  48.     {
  49.         int x;
  50.         cin >> x;
  51.  
  52.         if ((int)adj[x].size() >= block)
  53.         {
  54.             for (auto i : adj[x])
  55.             {
  56.                 if ((int)adj[i.first].size() < block)
  57.                     break;
  58.                 if (cv[x] ^ c[i.second] ^ cv[i.first])
  59.                 {
  60.                     --cnt[i.first][1];
  61.                     ++cnt[i.first][0];
  62.                 }
  63.                 else
  64.                 {
  65.                     --cnt[i.first][0];
  66.                     ++cnt[i.first][1];
  67.                 }
  68.             }
  69.  
  70.             cv[x] ^= 1;
  71.             ans = ans - cnt[x][1] + cnt[x][0];
  72.             swap(cnt[x][0], cnt[x][1]);
  73.         }
  74.         else
  75.         {
  76.             for (auto i : adj[x])
  77.             {
  78.                 if (c[i.second] ^ cv[i.first])
  79.                 {
  80.                     --ans;
  81.                     --cnt[i.first][1];
  82.                     ++cnt[i.first][0];
  83.                 }
  84.                 else
  85.                 {
  86.                     ++ans;
  87.                     --cnt[i.first][0];
  88.                     ++cnt[i.first][1];
  89.                 }
  90.                 c[i.second] ^= 1;
  91.             }
  92.         }
  93.  
  94.         cout << ans << " ";
  95.     }
  96. }
  97.  
  98. int32_t main()
  99. {
  100.     ios_base::sync_with_stdio(0);
  101.     cin.tie(0);
  102.     cout.tie(0);
  103.     if (fopen(task ".INP", "r"))
  104.     {
  105.         freopen(task ".INP", "r", stdin);
  106.         freopen(task ".OUT", "w", stdout);
  107.     }
  108.     Read();
  109.     Solve();
  110. }
  111.  
Advertisement
Add Comment
Please, Sign In to add comment