| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 255105 | Atalasion | 다리 (APIO19_bridges) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//khodaya khodet komak kon
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 100000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;
const int SQ = 150;
struct tagh{
int v, SZ, PAR;
};
vector<tagh> Ch;
struct query{
int id, PAR, w;
};
int n, m, q, W[N], E[N], V[N], U[N], par[N], sz[N], w[N], ans[N], mark[N], mark2[N];
vector<query> L[N];
pair<int, pii> Q[N];
bool cmp(int x, int y){
return W[x] > W[y];
}
int getpar(int v){
return (par[v] == v?v:getpar(par[v]));
}
inline void merge(int v, int u){
v = getpar(v), u = getpar(u);
if (v == u) return;
if (sz[v] < sz[u]) swap(v, u);
tagh res;
res.v = u;
res.SZ = sz[u];
Ch.pb(res);
res.v = v;
res.SZ = sz[v];
Ch.pb(res);
sz[v] += sz[u];
par[u] = v;
}
inline void Solve(query q, int l, int r){
vector<int> edge;
for (int i = q.id; i >= l; i--){
if (Q[i].F == 1){
if (!mark2[Q[i].S.F]){
w[Q[i].S.F] = Q[i].S.S, mark2[Q[i].S.F] = 1;
if (w[Q[i].S.F] >= q.w) edge.pb(Q[i].S.F);
}
}
}
for (int i = q.id; i < r; i++){
if (Q[i].F == 1){
if (!mark2[Q[i].S.F]){
mark2[Q[i].S.F] = 1;
if (W[Q[i].S.F] >= q.w) edge.pb(Q[i].S.F);
}
}
}
= Ch.clear();
for (int i = l; i <= r; i++) mark2[Q[i].S.F] = 0;
for (auto u:edge){
merge(V[u], U[u]);
}
ans[q.id] = sz[getpar(q.v)];
reverse(all(Ch));
for (auto u:Ch){
par[u.v] = u.v;
sz[u.v] = u.SZ;
}
Ch.clear();
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++){
int v,u, w;
cin >> v >> u >> w;
E[i] = i;
W[i] = w;
V[i] = v;
U[i] = u;
}
sort(E + 1, E + m + 1, cmp);
cin >> q;
for (int i = 0; i< q; i++){
sort(E + 1, E + m + 1, cmp);
memset(mark, 0, sizeof mark);
if (i * SQ >= q) break;
for (int j = 0; j < 50010; j++) L[j].clear(), L[j].shrink_to_fit();
for (int j = i * SQ; j < min(q, (i + 1) * SQ); j++){
int t, v, u;
cin >> t >> v >> u;
Q[j] = {t, {v, u}};
if (t == 2){
int l = 0, r = m + 1;
while (r - l > 1){
int md = (l + r) >> 1;
if (W[E[md]] < u) r = md;
else l = md;
}
query q;
q.id = j;
q.v = v;
q.w = u;
L[l].pb(q);
// cout << l << '\n';
}else{
mark[v] = 1;
}
}
for (int j = 1; j <= n; j++) par[j] = j, sz[j] = 1;
for (int j = 0; j <= m; j++){
if (!mark[E[j]]){
// cout << "E " << V[E[j]] << ' ' << U[E[j]] << '\n';
merge(V[E[j]], U[E[j]]);
}
for (auto u:L[j]){
Solve(u, i * SQ, min(q, (i + 1) * SQ));
}
}
for (int j = i * SQ; j < min(q, (i + 1) * SQ); j++) if(Q[j].F == 1) W[Q[j].S.F] = Q[j].S.S;
}
for (int i = 0; i < q; i++){
if (Q[i].F == 2) cout << ans[i] << '\n';
}
return 0;
}
/*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
5
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
*/