| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1045638 | mychecksedad | 다리 (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
struct Dsu {
vector<int> s, p;
vector<pair<int,int>> poop;
int sz;
Dsu(int n){
sz = n;
s.resize(n+1, 1);
p.resize(n+1);
for(int i = 0; i <= n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return find(p[v]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(s[a] > s[b]){
swap(a, b);
}
s[b] += s[a];
p[a] = b;
poop.pb({a, b});
}else{
poop.pb({-1, -1
});
}
}
void rollback(){
if(poop.size() == 0) return;
if(poop.back().ff == -1){
poop.pop_back();
return;
}
int a = poop.back().ff;
int b = poop.back().ss;
poop.pop_back();
p[a] = a;
s[b] -= s[a];
}
};
int n, m, q;
vector<arra<int, 4>> edges;
int S = 220;
void solve(){
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u, v, w; cin >> u >> v >> w;
edges.pb({w, v, u, i});
}
sort(all(edges), greater<array<int, 4>>());
vector<int> pos(m);
vector<int> used(m);
cin >> q;
int pu = 0;
for(int y = 0; y < q; y += S){
for(int i = 0; i < m; ++i) pos[edges[i][3]] = i;
int k = min(q, y+S) - y;
vector<array<int, 3>> upd;
vector<array<int, 4>> qr;
int qq = 0;
for(int j = 0; j < k; ++j){
int t, u, v; cin >> t >> u >> v;
if(t == 1){
--u;
upd.pb({v, u, j});
}else{
qr.pb({v, u, j, qq++});
}
}
vector<int> ans(qq);
Dsu d(n);
// sort(all(upd), greater<array<int, 3>>());
sort(all(qr), greater<array<int, 4>>());
int pu = 0;
for(int l = 0; l < upd.size(); ++l) used[upd[l][1]] = 1;
// for(auto f: qr){
// cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';
// }
for(int j = 0; j < qq; ++j){
int w = qr[j][0];
// cout << w << " : q\n" ;
while(pu < edges.size() && edges[pu][0] >= w){
if(used[edges[pu][3]]) ++pu;
else{
d.merge(edges[pu][1], edges[pu][2]);
// cout << edges[pu][3] << " : upd" << '\n';
++pu;
}
}
int roll = 0;
for(int l = int(upd.size()) - 1; l >= 0; --l){
int idx = upd[l][1];
if(used[idx] == 2) continue;
if(upd[l][2] < qr[j][2]){
used[idx] = 2;
if(upd[l][0] >= qr[j][0]){
++roll;
d.merge(edges[pos[idx]][1], edges[pos[idx]][2]);
}
}else{
if(edges[pos[idx]][0] >= qr[j][0]){
++roll;
d.merge(edges[pos[idx]][1], edges[pos[idx]][2]);
}
}
}
for(int l = int(upd.size()) - 1; l >= 0; --l){
int idx = upd[l][1];
used[idx] = 1;
}
// cout << qr[j][1] << ' ';
ans[qr[j][3]] = d.s[d.find(qr[j][1])];
for(int l = 0; l < roll; ++l){
d.rollback();
}
}
for(int l = 0; l < upd.size(); ++l) used[upd[l][1]] = 0;
for(auto x: ans) cout << x << '\n';
for(auto p: upd){
edges[pos[p[1]]][0] = p[0];
}
sort(all(edges), greater<array<int, 4>>());
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}