| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 511225 | blue | 다리 (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
const int rt = 1000;
int n, m;
vi u, v, w;
int q;
vi t;
vi b, r;
vi s, c;
struct change
{
int u;
int op;
int typ;
};
struct disjoint_set
{
vi parent;
vi subtree;
vector<change> changes; //node, type(0/1)
disjoint_set()
{
parent = vi(1+n);
subtree = vi(1+n, 1);
for(int i = 0; i <= n; i++) parent[i] = i;
}
int root(int u)
{
if(parent[u] == u) return u;
else if(parent[parent[u]] == parent[u]) return parent[u];
else
{
changes.push_back({u, parent[u], 0});
parent[u] = root(parent[u]);
return parent[u];
}
}
void join(int u, int v)
{
changes.push_back({-1, -1, -1});
u = root(u);
v = root(v);
if(u == v)
{
// cerr << "change rejected\n";
changes.push_back({0, 0, 0});
}
else
{
if(subtree[u] < subtree[v]) swap(u, v);
changes.push_back({v, parent[v], 1});
parent[v] = u;
subtree[u] += subtree[v];
changes.push_back(v);
// cerr << "making " << u << " parent of " << v << '\n';
}
}
void rollback()
{
while(1)
{
int u = changes.back().u;
int op = changes.back().op;
int typ = changes.back().typ;
changes.pop_back();
if(u == -1) return;
if(typ == 1)
{
subtree[parent[u]] -= subtree[u];
parent[u] = op;
}
else
{
parent[u] = op;
}
}
}
int reach(int u)
{
return subtree[root(u)];
}
};
int wt(int d)
{
if(d > 0)
{
return w[d];
}
else
{
return c[-d];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
u = v = w = vi(1+m);
for(int e = 1; e <= m; e++) cin >> u[e] >> v[e] >> w[e];
cin >> q;
t = b = r = s = c = vi(q);
for(int j = 0; j < q; j++)
{
cin >> t[j];
if(t[j] == 1) cin >> b[j] >> r[j];
else cin >> s[j] >> c[j];
}
vi ans(q, -1);
vi temp_edge_found(1+m, 0);
for(int bl = 0; bl <= (q-1)/rt; bl++)
{
int y = rt*bl;
int z = min(rt*(bl+1)-1, q-1);
// cerr << "current block = " << y << ' ' << z << '\n';
vi mod(1+m);
for(int j = y; j <= z; j++)
if(t[j] == 1)
mod[b[j]] = 1;
vi ops;
for(int e = 1; e <= m; e++)
if(!mod[e])
ops.push_back(e);
for(int j = y; j <= z; j++)
if(t[j] == 2)
ops.push_back(-j);
sort(ops.begin(), ops.end(), [] (int d, int f)
{
int wd = wt(d), wf = wt(f);
if(wd != wf) return wd > wf;
else return d > f;
});
disjoint_set dsu;
for(int o: ops)
{
// cerr << "\n\n\n";
if(o > 0)
{
dsu.join(u[o], v[o]);
// cerr << "general join: " << o << '\n';
}
else
{
int qr = -o;
int curr_ct = 0;
// cerr << "answering query : " << qr << '\n';
for(int l = qr-1; l >= y; l--)
{
if(t[l] == 2) continue;
if(temp_edge_found[b[l]]) continue;
temp_edge_found[b[l]] = 1;
if(r[l] >= c[qr])
{
// cerr << "query specific join 1: " << b[l] << '\n';
dsu.join(u[b[l]], v[b[l]]);
curr_ct++;
}
}
for(int l = qr+1; l <= z; l++)
{
// cerr << "l = " << l << '\n';
if(t[l] == 2) continue;
if(temp_edge_found[b[l]]) continue;
// cerr << "success!\n";
temp_edge_found[b[l]] = 1;
// cerr << b[l] << " > " << w[b[l]] << ' ' << c[qr] << '\n';
if(w[b[l]] >= c[qr])
{
// cerr << "query specific join 2: " << b[l] << '\n';
dsu.join(u[b[l]], v[b[l]]);
curr_ct++;
}
}
ans[qr] = dsu.reach(s[qr]);
for(int ct = 0; ct < curr_ct; ct++)
{
// cerr << "rollback\n";
dsu.rollback();
}
for(int l = y; l <= z; l++)
{
if(t[l] == 1)
{
temp_edge_found[b[l]] = 0;
}
}
}
}
for(int l = y; l <= z; l++)
{
if(t[l] == 1)
{
w[b[l]] = r[l];
}
}
}
for(int j = 0; j < q; j++)
if(t[j] == 2)
cout << ans[j] << '\n';
}