제출 #960664

#제출 시각아이디문제언어결과실행 시간메모리
960664MisterReaper다리 (APIO19_bridges)C++17
59 / 100
3039 ms59620 KiB
#include <bits/stdc++.h> using i64 = long long; constexpr int maxN = 5E4 + 5; std::vector<std::pair<int, int>> operations; int par[maxN], sz[maxN]; void reset() { std::iota(par, par + maxN, 0); std::fill(sz, sz + maxN, 1); operations.clear(); } int get(int a) { if(par[a] == a) { return a; } return get(par[a]); } bool unite(int u, int v) { u = get(u), v = get(v); if(u == v) { return false; } if(sz[u] > sz[v]) { std::swap(u, v); } par[u] = v; sz[v] += sz[u]; operations.emplace_back(u, v); return true; } void rollback() { auto [u, v] = operations.back(); operations.pop_back(); par[u] = u; sz[v] -= sz[u]; } int size(int a) { return sz[get(a)]; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<bool> changed; std::vector<int> u(m), v(m), w(m); for(int i = 0; i < m; i++) { std::cin >> u[i] >> v[i] >> w[i]; u[i]--, v[i]--; } int q; std::cin >> q; std::vector<int> t(q), x(q), y(q); for(int i = 0; i < q; i++) { std::cin >> t[i] >> x[i] >> y[i]; x[i]--; } constexpr int B = 350; std::vector<std::vector<int>> deck(q); std::vector<int> ans(q); for(int l = 0; l < q; l += B) { int r = std::min(q, l + B); changed.assign(m, false); reset(); std::vector<int> ask; for(int i = l; i < r; i++) { if(t[i] == 1) { changed[x[i]] = true; } else { ask.emplace_back(i); } } std::vector<int> edges, able; for(int i = 0; i < m; i++) { if(!changed[i]) { edges.emplace_back(i); } else { able.emplace_back(i); } } for(int i = l; i < r; i++) { if(t[i] == 1) { w[x[i]] = y[i]; } else { for(int j : able) { if(y[i] <= w[j]) { deck[i].emplace_back(j); } } } } std::sort(edges.begin(), edges.end(), [&](int lhs, int rhs) -> bool { return w[lhs] > w[rhs]; }); std::sort(ask.begin(), ask.end(), [&](int lhs, int rhs) -> bool { return y[lhs] > y[rhs]; }); int p = 0; for(int i : ask) { while(p != edges.size() && w[edges[p]] >= y[i]) { unite(u[edges[p]], v[edges[p]]); p++; } int ps = operations.size(); for(int j : deck[i]) { unite(u[j], v[j]); } ans[i] = size(x[i]); while(operations.size() != ps) { rollback(); } deck[i].clear(); } } for(int i = 0; i < q; i++) { if(t[i] == 2) { std::cout << ans[i] << '\n'; } } return 0; }

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

bridges.cpp: In function 'int main()':
bridges.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             while(p != edges.size() && w[edges[p]] >= y[i]) {
      |                   ~~^~~~~~~~~~~~~~~
bridges.cpp:125:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |             while(operations.size() != ps) {
      |                   ~~~~~~~~~~~~~~~~~~^~~~~
#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...