제출 #258356

#제출 시각아이디문제언어결과실행 시간메모리
258356DS007다리 (APIO19_bridges)C++14
59 / 100
3030 ms91792 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e4 + 5, M = 1e5, Q = 1e5, BS = 500; int sz[N], par[N]; stack<int> s; void reset() { iota(par, par + N, 0); fill(sz, sz + N, 1); } int find(int x) { if (x == par[x]) return x; return find(par[x]); } void merge(int x, int y) { int px = find(x), py = find(y); if (px == py) return; if (sz[px] < sz[py]) swap(px, py); sz[px] += sz[py]; par[py] = px; s.push(py); } void rollback(int x) { while (s.size() > x) { int temp = s.top(); s.pop(); sz[par[temp]] -= sz[temp]; par[temp] = temp; } } int u[M], v[M], d[M], t[Q], x[Q], y[Q], ans[Q], n, m, q; int solveTestCase() { cin >> n >> m; for (int i = 0; i < m; i++) cin >> u[i] >> v[i] >> d[i]; cin >> q; for (int i = 0; i < q; i++) cin >> t[i] >> x[i] >> y[i]; for (int i = 0; i < q; i++) { if (t[i] == 1) x[i]--; } for (int i = 0; i < q; i += BS) { int l = i, r = min(q - 1, i + BS - 1); bool changed[m] = {}; vector<int> unchanged, updates, ask; for (int j = l; j <= r; j++) { if (t[j] == 1) changed[x[j]] = true, updates.push_back(x[j]); else ask.push_back(j); } for (int i = 0; i < m; i++) { if (!changed[i]) unchanged.push_back(i); } vector<int> join[BS]; for (int j = l; j <= r; j++) { if (t[j] == 1) { d[x[j]] = y[j]; } else { for (int k : updates) { if (d[k] >= y[j]) join[j - l].push_back(k); } } } sort(unchanged.begin(), unchanged.end(), [&](auto a, auto b) { return d[a] > d[b]; }); sort(ask.begin(), ask.end(), [&](auto a, auto b) { return y[a] > y[b]; }); reset(); int ptr = 0; for (int j : ask) { while (ptr != unchanged.size() && d[unchanged[ptr]] >= y[j]) merge(u[unchanged[ptr]], v[unchanged[ptr]]), ptr++; int temp = s.size(); for (int k : join[j - l]) merge(u[k], v[k]); ans[j] = sz[find(x[j])]; rollback(temp); } } for (int i = 0; i < q; i++) { if (t[i] == 2) cout << ans[i] << " \n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while (t--) solveTestCase(); }

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

bridges.cpp: In function 'void rollback(long long int)':
bridges.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (s.size() > x) {
            ~~~~~~~~~^~~
bridges.cpp: In function 'long long int solveTestCase()':
bridges.cpp:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr != unchanged.size() && d[unchanged[ptr]] >= y[j])
                    ~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:115:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#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...