제출 #255124

#제출 시각아이디문제언어결과실행 시간메모리
255124Atalasion다리 (APIO19_bridges)C++14
13 / 100
3093 ms6568 KiB
//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 = 130; struct tagh{ int v, SZ; }; vector<tagh> Ch; struct query{ int id, v, 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 <= m; 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...