| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 159335 | iefnah06 | Werewolf (IOI18_werewolf) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
// 把操作分块，每次回答每块内询问的答案
// 对于块前面的修改，把询问和这些修改按照边权降序排序，把前面的修改直接用并查集合并
// 对于块内的，暴力建图计算影响
const int MAXN = 2e5;
int N, M;
int S;
int A[MAXN], B[MAXN], C[MAXN];
int Q;
int T[MAXN], X[MAXN], Y[MAXN];
int ans[MAXN];
bool vis[MAXN];
struct dsu {
int par[MAXN], sz[MAXN];
int getpar(int a) {
return par[a] == -1 ? a : (par[a] = getpar(par[a]));
}
void merge(int a, int b) {
a = getpar(a), b = getpar(b);
if (a != b) {
if (sz[a] > sz[b]) swap(a, b);
sz[b] += sz[a];
par[a] = b;
}
}
void reset() {
fill(par + 1, par + N + 1, -1);
fill(sz + 1, sz + N + 1, 1);
}
int size(int a) const {
return sz[a];
}
} conn;
vector<int> adj[MAXN];
void add(int a, int b) {
assert(1 <= a && a <= N);
assert(1 <= b && b <= N);
a = conn.getpar(a), b = conn.getpar(b);
adj[a].push_back(b);
adj[b].push_back(a);
}
int dfs(int cur) {
vis[cur] = true;
int res = conn.size(cur);
for (int nxt : adj[cur]) {
if (!vis[nxt]) {
res += dfs(nxt);
}
}
return res;
}
int main() {
scanf("%d %d", &N, &M);
S = max(1, int(sqrt(N * log2(N))));
for (int i = 0; i < M; i++) {
scanf("%d %d %d", &A[i], &B[i], &C[i]);
}
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
scanf("%d %d %d", &T[i], &X[i], &Y[i]);
if (T[i] == 1) X[i]--;
}
for (int st = 0; st < Q; st += S) {
int ed = min(Q, st + S);
vector<pair<int, int>> evts;
for (int i = st; i < ed; i++) {
if (T[i] == 1) {
vis[X[i]] = true;
} else {
evts.emplace_back(Y[i], ~i); // < 0
}
}
vector<int> special;
for (int i = 0; i < M; i++) {
if (vis[i]) {
special.push_back(i);
} else {
evts.emplace_back(C[i], i); // >= 0
}
}
for (int i = st; i < ed; i++) {
if (T[i] == 1) {
vis[X[i]] = false;
}
}
sort(evts.begin(), evts.end(), greater<pair<int, int>>());
conn.reset();
for (const auto& ev : evts) {
int w, i; tie(w, i) = ev;
if (i >= 0) {
conn.merge(A[i], B[i]);
} else {
i = ~i;
for (int j = i - 1; j >= st; j--) {
if (T[j] != 1 || vis[X[j]]) continue;
vis[X[j]] = true;
if (Y[j] >= w) {
add(A[X[j]], B[X[j]]);
}
}
for (const auto& j : special) {
if (vis[j]) {
vis[j] = false;
} else if (C[j] >= w) {
add(A[j], B[j]);
}
}
ans[i] = dfs(conn.getpar(X[i]));
// reset
vis[conn.getpar(X[i])] = false;
for (const auto& j : special) {
int a = conn.getpar(A[j]);
int b = conn.getpar(B[j]);
adj[a].clear(), adj[b].clear();
vis[a] = false, vis[b] = false;
}
}
}
for (int i = st; i < ed; i++) {
if (T[i] == 1) {
C[X[i]] = Y[i];
}
}
}
for (int i = 0; i < Q; i++) {
if (T[i] == 2) {
printf("%d\n", ans[i]);
}
}
return 0;
}