Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "LIGHT"
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- using namespace std;
- using ll = long long;
- using ld = long double;
- constexpr int N = 1e5 + 2;
- constexpr int block = 320;
- constexpr int Inf = 1e9 + 7;
- int n, m, q;
- vector<pair<int, int>> adj[N];
- int c[N], cnt[N][2], ans(0), cv[N];
- // 1 : xenh
- // 0 : do
- void Read()
- {
- cin >> n >> m >> q;
- for (int i = 1; i <= m; ++i)
- {
- int u, v;
- cin >> u >> v >> c[i];
- adj[u].emplace_back(v, i);
- adj[v].emplace_back(u, i);
- ++cnt[u][c[i]];
- ++cnt[v][c[i]];
- ans += c[i];
- }
- }
- void Solve()
- {
- for (int i = 1; i <= n; ++i)
- sort(adj[i].begin(), adj[i].end(), [&](const pair<int, int> &x, const pair<int, int> &y)
- { return adj[x.first].size() > adj[y.first].size(); });
- while (q--)
- {
- int x;
- cin >> x;
- if ((int)adj[x].size() >= block)
- {
- for (auto i : adj[x])
- {
- if ((int)adj[i.first].size() < block)
- break;
- if (cv[x] ^ c[i.second] ^ cv[i.first])
- {
- --cnt[i.first][1];
- ++cnt[i.first][0];
- }
- else
- {
- --cnt[i.first][0];
- ++cnt[i.first][1];
- }
- }
- cv[x] ^= 1;
- ans = ans - cnt[x][1] + cnt[x][0];
- swap(cnt[x][0], cnt[x][1]);
- }
- else
- {
- for (auto i : adj[x])
- {
- if (c[i.second] ^ cv[i.first])
- {
- --ans;
- --cnt[i.first][1];
- ++cnt[i.first][0];
- }
- else
- {
- ++ans;
- --cnt[i.first][0];
- ++cnt[i.first][1];
- }
- c[i.second] ^= 1;
- }
- }
- cout << ans << " ";
- }
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment