제출 #548601

#제출 시각아이디문제언어결과실행 시간메모리
548601GioChkhaidze다리 (APIO19_bridges)C++14
44 / 100
3062 ms5840 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define s second using namespace std; const int N = 1e5 + 5; bool used[N], T; int n, m, q, ms; int ans[N], p[N], sz[N], lc[N], cl[N]; int a[N], b[N], c[N], t[N], x[N], y[N]; vector < pair < int , pair < int , int > > > rec; int P(int x) { if (x == p[x]) return x; if (T) rec.pb({x, {sz[x], p[x]}}); return p[x] = P(p[x]); } void uni(int a, int b) { a = P(a), b = P(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); if (T) rec.pb({a, {sz[a], p[a]}}); if (T) rec.pb({b, {sz[b], p[b]}}); sz[a] += sz[b]; p[b] = a; return ; } void roll_back() { while (rec.size()) { int x = rec.back().f; sz[x] = rec.back().s.f; p[x] = rec.back().s.s; rec.pop_back(); } } main () { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> a[i] >> b[i] >> c[i]; lc[i] = c[i]; } cin >> q; ms = 1000; for (int i = 1; i <= q; ++i) { cin >> t[i] >> x[i] >> y[i]; } vector < pair < pair < int , int > , int > > s; for (int i = 1; i <= q; i += ms) { vector < int > rc; int rm = min(i + ms - 1, q); for (int j = i; j <= rm; ++j) { if (t[j] == 1) { if (!used[x[j]]) rc.pb(x[j]); used[x[j]] = true; } else if (t[j] == 2) { s.pb({{y[j], 0}, j}); } } for (int j = 1; j < i; ++j) { if (t[j] == 2) continue; lc[x[j]] = y[j]; } for (int j = 1; j <= m; ++j) { if (used[j]) { cl[j] = lc[j]; continue; } s.pb({{lc[j], 1}, j}); } sort(s.begin(), s.end()); for (int j = 1; j <= n; ++j) { p[j] = j, sz[j] = 1; } for (int j = s.size() - 1; j >= 0; --j) { int tp = s[j].f.s; int cst = s[j].f.f; int id = s[j].s; if (tp) { uni(a[id], b[id]); } else { T = true; for (int k = i; k <= id; ++k) { if (t[k] == 1) lc[x[k]] = y[k]; } for (int k = 0; k < rc.size(); ++k) { int idx = rc[k]; if (cst <= lc[idx]) { uni(a[idx], b[idx]); } lc[idx] = cl[idx]; } ans[id] = sz[P(x[id])]; roll_back(); T = false; } } for (int j = i; j <= rm; ++j) { if (t[j] == 1) used[x[j]] = false; } s.clear(); } for (int i = 1; i <= q; ++i) { if (t[i] == 2) cout << ans[i] << "\n"; } }

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

bridges.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main () {
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int k = 0; k < rc.size(); ++k) {
      |                     ~~^~~~~~~~~~~
#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...