제출 #872148

#제출 시각아이디문제언어결과실행 시간메모리
872148Kihihihi다리 (APIO19_bridges)C++17
73 / 100
3038 ms12396 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <cmath> #include <numeric> #include <ctime> #include <chrono> #include <random> #include <cassert> #include <vector> #include <string> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <deque> #include <bitset> using namespace std; mt19937_64 rnd(time(NULL)); #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("vpt") #pragma GCC optimize("rename-registers") #pragma GCC optimize("move-loop-invariants") #pragma GCC optimize("unswitch-loops") #pragma GCC optimize(3) #pragma GCC optimize("inline") const int SQ = 1200; struct edge { int a, b, w; }; struct query { int qt, x, y; }; struct dsu { int n; vector<int> p, rk, sz; vector<vector<pair<int*, int>>> hist; dsu(int in) { n = in; p.resize(n); iota(p.begin(), p.end(), 0); rk.resize(n); sz.resize(n, 1); } int rt(int v) { return (p[v] == v ? v : rt(p[v])); } void unite(int a, int b) { a = rt(a); b = rt(b); hist.push_back({}); if (a == b) { return; } hist.back().reserve(4); if (rk[a] < rk[b]) { swap(a, b); } hist.back().push_back({ &p[b], p[b] }); p[b] = a; hist.back().push_back({ &sz[a], sz[a] }); sz[a] += sz[b]; hist.back().push_back({ &sz[b], sz[b] }); sz[b] = 0; hist.back().push_back({ &rk[a], rk[a] }); rk[a] += (rk[a] == rk[b]); } void ctrlz() { while (hist.back().size()) { *hist.back().back().first = hist.back().back().second; hist.back().pop_back(); } hist.pop_back(); } int get(int v) { return sz[rt(v)]; } }; void solve() { int n, m; vector<edge> e; cin >> n >> m; e.resize(m); for (int i = 0; i < m; i++) { cin >> e[i].a >> e[i].b >> e[i].w; e[i].a--; e[i].b--; } int q; cin >> q; for (int qli = 0; qli < q; qli += SQ) { int qri = qli + SQ - 1; qri = min(qri, q - 1); vector<query> qr(qri - qli + 1); vector<bool> used(m); for (int i = 0; i < qr.size(); i++) { cin >> qr[i].qt >> qr[i].x >> qr[i].y; qr[i].x--; if (qr[i].qt == 1) { used[qr[i].x] = true; } } vector<int> eu, notu; for (int i = 0; i < m; i++) { if (used[i]) { eu.push_back(i); } else { notu.push_back(i); } } sort(notu.begin(), notu.end(), [&](int x, int y) { return e[x].w < e[y].w; } ); vector<vector<int>> add; vector<tuple<int, int, int>> ask; for (int i = 0; i < qr.size(); i++) { if (qr[i].qt == 1) { e[qr[i].x].w = qr[i].y; continue; } ask.push_back({ qr[i].y, qr[i].x, add.size() }); add.push_back({}); for (auto& j : eu) { if (e[j].w >= qr[i].y) { add.back().push_back(j); } } } sort(ask.rbegin(), ask.rend()); dsu kek(n); vector<int> ans(ask.size(), -1); for (auto& [w, ver, idx] : ask) { while (notu.size() && e[notu.back()].w >= w) { kek.unite(e[notu.back()].a, e[notu.back()].b); notu.pop_back(); } for (auto& i : add[idx]) { kek.unite(e[i].a, e[i].b); } ans[idx] = kek.get(ver); for (int _ = 0; _ < add[idx].size(); _++) { kek.ctrlz(); } } for (int i = 0; i < ans.size(); i++) { cout << ans[i] << "\n"; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); return 0; } /* */

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

bridges.cpp: In function 'void solve()':
bridges.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int i = 0; i < qr.size(); i++)
      |                         ~~^~~~~~~~~~~
bridges.cpp:155:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for (int i = 0; i < qr.size(); i++)
      |                         ~~^~~~~~~~~~~
bridges.cpp:190:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |             for (int _ = 0; _ < add[idx].size(); _++)
      |                             ~~^~~~~~~~~~~~~~~~~
bridges.cpp:195:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |         for (int i = 0; i < ans.size(); 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...