제출 #198032

#제출 시각아이디문제언어결과실행 시간메모리
198032QCFium다리 (APIO19_bridges)C++14
100 / 100
2124 ms12392 KiB
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } int64_t rs64() { long long n; scanf("%lld", &n); return n; } struct UnionFind { std::vector<int> data; std::vector<int> size; std::vector<std::vector<std::pair<int, int> > > hens; UnionFind (int n) : data(n, -1), size(n, 0), hens(n) {} void add_hen(int start, int end, int index) { hens[start].push_back({index, end}); } int root(int i) { return data[i] < 0 ? i : data[i] = root(data[i]); } bool unite(int i, int j) { i = root(i); j = root(j); if (i == j) return false; if (-data[i] + size[i] > -data[j] + size[j]) std::swap(i, j); // i->j hens[j].reserve(hens[j].size() + hens[i].size()); for (auto k : hens[i]) hens[j].push_back(k); hens[i].clear(); size[j] += size[i]; data[j] += data[i]; data[i] = j; return true; } int get_size(int i) { return -data[root(i)]; } }; int main() { int n = ri(), m = ri(); struct Hen { int a; int b; int cost; int id; }; std::vector<Hen> hens(m); for (int i = 0; i < m; i++) hens[i].a = ri() - 1, hens[i].b = ri() - 1, hens[i].cost = ri(), hens[i].id = i; struct Query { int type; int index; int cost; int id; }; int q = ri(); std::vector<Query> qs(q); for (int i = 0; i < q; i++) qs[i].type = ri() - 1, qs[i].index = ri() - 1, qs[i].cost = ri(), qs[i].id = i; #define BLOCK 1000 std::vector<bool> changing(m); std::vector<int> cost(m); std::vector<int> h_start(m), h_end(m); for (int i = 0; i < m; i++) cost[hens[i].id] = hens[i].cost, h_start[hens[i].id] = hens[i].a, h_end[hens[i].id] = hens[i].b; std::vector<int> ch_rollback; std::vector<bool> used(n); std::vector<int> used_rollback; std::vector<int> res(q); for (int i = 0; i < q; i += BLOCK) { auto hens_copy = hens; std::sort(hens_copy.begin(), hens_copy.end(), [] (auto &i, auto &j) { return i.cost > j.cost; }); std::vector<Query> local; local.reserve(std::min(q, i + BLOCK) - i); for (int j = i; j < q && j < i + BLOCK; j++) { local.push_back(qs[j]); if (!qs[j].type) ch_rollback.push_back(qs[j].index), changing[qs[j].index] = true; } std::sort(local.begin(), local.end(), [] (auto &i, auto &j) { return i.cost > j.cost; }); UnionFind uni(n); for (int j = 0; j < m; j++) if (changing[j]) uni.add_hen(h_start[j], h_end[j], j), uni.add_hen(h_end[j], h_start[j], j); int head = 0; for (auto j : local) { if (!j.type) continue; static std::vector<std::pair<int, int> > rollback; for (int k = i; k < j.id; k++) if (!qs[k].type) rollback.push_back({qs[k].index, cost[qs[k].index]}), cost[qs[k].index] = qs[k].cost; while (head < m && hens_copy[head].cost >= j.cost) { if (!changing[hens_copy[head].id]) uni.unite(hens_copy[head].a, hens_copy[head].b); head++; } auto use = [&] (int i) { used_rollback.push_back(i); used[i] = true; return i; }; std::queue<int> que; que.push(use(uni.root(j.index))); int cur = 0; while (que.size()) { int k = que.front(); que.pop(); cur += -uni.data[k]; for (auto l : uni.hens[k]) { if (cost[l.first] < j.cost) continue; int target = uni.root(l.second); if (!used[target]) { use(target); que.push(target); } } } res[j.id] = cur; for (auto k : used_rollback) used[k] = false; used_rollback.clear(); for (; rollback.size(); rollback.pop_back()) cost[rollback.back().first] = rollback.back().second; } for (int j = i; j < q && j < i + BLOCK; j++) { if (!qs[j].type) { cost[qs[j].index] = qs[j].cost; hens[qs[j].index].cost = qs[j].cost; } } for (auto i : ch_rollback) changing[i] = false; ch_rollback.clear(); } for (int i = 0; i < q; i++) if (qs[i].type) printf("%d\n", res[i]); return 0; }

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

bridges.cpp: In function 'int ri()':
bridges.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bridges.cpp: In function 'int64_t rs64()':
bridges.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
#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...