제출 #562681

#제출 시각아이디문제언어결과실행 시간메모리
562681hhhhaura다리 (APIO19_bridges)C++14
0 / 100
3074 ms11212 KiB
#define wiwihorz #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("sse") #pragma loop-opt(on) #define rep(i, a, b) for(int i = a; i <= b; i ++) #define rrep(i, a, b) for(int i = b; i >= a; i --) #define all(x) x.begin(), x.end() #define ceil(a, b) ((a + b - 1) / (b)) #define int long long int #define lld long double #define pii pair<int, int> #define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()) #define INF 1000000000000000000 #define MOD 1000000007 #define eps (1e-9) using namespace std; #ifdef wiwihorz #define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a) void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; } void kout() { cerr << endl; } template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);} #else #define print(...) 0 #define vprint(...) 0 #endif #define x first #define y second namespace solver { int n, m, q, sz = 100000, bk, cnt; vector<pair<pii, int>> v; vector<vector<int>> mp; vector<int> ans, x, y, cost, tp, s; vector<int> ord, vis, par, rk, bg, go; void init_(int _n, int _m) { n = _n, m = _m; x.assign(m + 1, 0); y.assign(m + 1, 0); cost.assign(m + 1, 0); ord.assign(m, 0); iota(all(ord), 1); mp.assign(n + 1, vector<int>()); go.assign(n + 1, 0); } void init2_(int _q) { q = _q, bk = ceil(q, sz); ans.assign(q + 1, 0); v.assign(q + 1, {{0, 0}, 0}); } int pos(int x) { if(par[par[x]] == par[x]) return par[x]; else return par[x] = pos(par[x]); } void unite(int a, int b) { int aa = pos(a); int bb = pos(b); if(aa == bb) return; if(rk[bb] > rk[aa]) swap(aa, bb); rk[aa] += (rk[aa] == rk[bb]); par[bb] = aa; bg[aa] += bg[bb]; } void build() { vis.assign(m + 1, 0); rk.assign(n + 1, 0); par.assign(n + 1, 0); bg.assign(n + 1, 1); iota(all(par), 0); s.clear(); tp.clear(); } void dfs(int x) { cnt += bg[pos(x)], go[pos(x)] = 1; for(auto i : mp[x]) { if(go[pos(i)]) continue; dfs(pos(i)); } } void solve() { sort(all(ord), [&](int a, int b) { return cost[a] > cost[b]; }); rep(i, 1, bk) { build(); int l = (i - 1) * sz + 1; int r = min(q, i * sz); rep(j, l, r) { if(v[j].y == 1) { vis[v[j].x.x] = 1; tp.push_back(v[j].x.x); } else s.push_back(j); } sort(all(s), [&](int a, int b) { return v[a].x.y > v[b].x.y; }); int ii = 0; vector<pii> ret; for(auto j : s) { ret.clear(); int id = v[j].x.x, val = v[j].x.y; rep(k, l, j - 1) if(v[k].y == 1) { int a = v[k].x.x, b = v[k].x.y; ret.push_back({a, cost[a]}); cost[a] = b; } while(ii < m && (vis[ord[ii]] || cost[ord[ii]] >= val)) { if(vis[ord[ii]]) { ii++; continue; } int cur = ord[ii]; unite(x[cur], y[cur]); ii++; } for(auto k : tp) if(cost[k] >= val) { int l = pos(x[k]), r = pos(y[k]); mp[l].push_back(r); mp[r].push_back(l); } cnt = 0, dfs(pos(id)); ans[j] = cnt; for(auto k : tp) { int l = pos(x[k]), r = pos(y[k]); go[l] = go[r] = 0; mp[l].clear(); mp[r].clear(); } for(auto k : ret) cost[k.x] = k.y; } rep(j, l, r) if(v[j].y == 1) { cost[v[j].x.x] = v[j].x.y; } vector<int> L, R(m, 0); for(auto j : ord) if(!vis[j]) L.push_back(j); auto cmp = [&](int a, int b) { return cost[a] > cost[b]; }; sort(all(tp), cmp); //merge(tp.begin(), tp.end(), L.begin(), L.end(), R.begin(), cmp); ord = R; } rep(i, 1, q) if(v[i].y == 2) { cout << ans[i] << "\n"; } } }; using namespace solver; signed main() { ios::sync_with_stdio(false), cin.tie(0); int n, m; cin >> n >> m; init_(n, m); rep(i, 1, m) cin >> x[i] >> y[i] >> cost[i]; int q; cin >> q; init2_(q); rep(i, 1, q) cin >> v[i].y >> v[i].x.x >> v[i].x.y; solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
bridges.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
bridges.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~
#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...