제출 #939694

#제출 시각아이디문제언어결과실행 시간메모리
939694HiepVu217다리 (APIO19_bridges)C++17
100 / 100
1782 ms34704 KiB
#include <bits/stdc++.h> #define FOR(i, x, y) for (int i = x; i < y; i++) using namespace std; const int N = 1e5 + 17, M = 1e3; int n, m, q; int u[N], v[N], w[N], t[N], x[N], y[N]; int par[N], sz[N], ans[N]; bool change[N]; vector <int> ed[N]; stack <int> rb; int root (int u) { while (u != par[u]) { u = par[u]; } return u; } void join (int u, int v) { int ru = root(u), rv = root(v); if (ru == rv) { return; } if (sz[ru] < sz[rv]) { swap (ru, rv); } rb.push(rv); par[rv] = ru; sz[ru] += sz[rv]; } void rollback (int x) { while (rb.size() > x) { int s = rb.top(); rb.pop(); sz[par[s]] -= sz[s]; par[s] = s; } } bool cmp1 (int a, int b) { return w[a] > w[b]; } bool cmp2 (int a, int b) { return y[a] > y[b]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> u[i] >> v[i] >> w[i]; } cin >> q; for (int i = 1; i <= q; ++i) { cin >> t[i] >> x[i] >> y[i]; } for (int l = 1; l <= q; l += M) { int r = min(q + 1, l + M); iota (par + 1, par + n + 1, 1); fill (sz + 1, sz + n + 1, 1); fill(change + 1, change + m + 1, false); vector<int> ask, upd, unchanged; FOR(i, l, r) { if (t[i] == 1) { change[x[i]] = true; upd.push_back(i); } else ask.push_back(i); } FOR(i, 1, m + 1) if (!change[i]) unchanged.push_back(i); FOR(i, l, r) { if (t[i] == 1) w[x[i]] = y[i]; else { ed[i - l].clear(); for (int j : upd) if (w[x[j]] >= y[i]) ed[i - l].push_back(x[j]); } } sort(ask.begin(), ask.end(), cmp2); sort(unchanged.begin(), unchanged.end(), cmp1); int ptr = 0; for (int i : ask) { while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) { join(u[unchanged[ptr]], v[unchanged[ptr]]); ptr++; } int prev_size = rb.size(); for (int j : ed[i - l]) join(u[j], v[j]); ans[i] = sz[root(x[i])]; rollback(prev_size); } } for (int i = 1; i <= q; ++i) { if (t[i] == 2) { cout << ans[i] << "\n"; } } }

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

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:36:19: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  while (rb.size() > x)
      |         ~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:96:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
      |           ~~~~^~~~~~~~~~~~~~~~~~
#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...