제출 #978826

#제출 시각아이디문제언어결과실행 시간메모리
978826ZHIRDILBILDIZ다리 (APIO19_bridges)C++14
13 / 100
1460 ms8472 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int, int> using namespace std; const int N = 5e4 + 10; const int B = 1000; int p[N]; int sz[N]; int ans[N]; vector<pair<int*, int>> hint; void init (int _sz) { hint.clear(); for (int i = 0; i < _sz; ++i) p[i] = i, sz[i] = 1; } int get (int u) { if (u != p[u]) return get(p[u]); return p[u]; } void join (int u, int v) { u = get(u); v = get(v); if (u == v) return; if (sz[u] > sz[v]) swap(u, v); hint.push_back({&sz[v], sz[v]}); hint.push_back({&p[u], u}); sz[v] += sz[u]; p[u] = v; } void rollback (int sz) { while (hint.size() > sz) { auto now = hint.back(); *now.fi = now.se; hint.pop_back(); } } signed main () { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; int u[m], v[m], w[m]; for (int i = 0; i < m; ++i) { cin >> u[i] >> v[i] >> w[i]; --u[i]; --v[i]; } int q; cin >> q; int type[q], x[q], y[q]; for (int i = 0; i < q; ++i) { cin >> type[i] >> x[i] >> y[i]; --x[i]; } vector<int> need[B]; for (int l = 0; l < q; l += B) { init(n); int r = min(q, l + B); vector<int> upd; vector<pii> ask, not_upd; bool us[m] = {}; bool abu[m] = {}; for (int j = l; j < r; ++j) if (type[j] == 1) { upd.push_back(j); us[x[j]] = 1; } else ask.push_back({y[j], j}); for (int i = 0; i < m; ++i) if (!us[i]) not_upd.push_back({w[i], i}); for (int j = l; j < r; ++j) if (type[j] == 1) w[x[j]] = y[j]; else { need[j - l].clear(); for (int q : upd) if (w[x[q]] >= y[j]) need[j - l].push_back(x[q]); } sort(not_upd.begin(), not_upd.end()); sort(ask.begin(), ask.end()); reverse(ask.begin(), ask.end()); int uk = (int)not_upd.size() - 1; for (auto j : ask) { while (uk >= 0 && not_upd[uk].fi >= j.fi) { int pos = not_upd[uk].se; join(u[pos], v[pos]); --uk; } int was = hint.size(); for (int q : need[j.se - l]) { join(u[q], v[q]); } ans[j.se] = sz[get(x[j.se])]; rollback(was); } } for (int i = 0; i < q; ++i) if (type[i] == 2) cout << ans[i] << '\n'; return 0; }

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

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:38:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     while (hint.size() > sz) {
      |            ~~~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:77:14: warning: unused variable 'abu' [-Wunused-variable]
   77 |         bool abu[m] = {};
      |              ^~~
#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...