제출 #253538

#제출 시각아이디문제언어결과실행 시간메모리
253538DystoriaX다리 (APIO19_bridges)C++14
100 / 100
2714 ms7064 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int, int> pii; struct Query{ int type, a, b, idx; }; const int sq = 750; int n, m, q; int p[50010], sz[50010]; pii edges[100010]; vector<int> eg; int w[100010]; Query qry[100010]; int ans[100010]; void init(){ iota(p, p + n + 1, 0); fill(sz, sz + n + 1, 1); } int findR(int x){ return p[x] == x ? x : p[x] = findR(p[x]); } void join(int a, int b){ a = findR(a), b = findR(b); if(a == b) return; if(sz[a] > sz[b]) swap(a, b); p[a] = b; sz[b] += sz[a]; } bool cmp(Query a, Query b){ return a.b > b.b; } bool egCmp(int a, int b){ return w[a] > w[b]; } vector<int> adj[50010]; bitset<100010> dead, vis, visited; vector<int> added; void add_edge(int idx){ int u, v; u = findR(edges[idx].fi), v = findR(edges[idx].se); if(u == v) return; added.emplace_back(idx); adj[u].emplace_back(v); adj[v].emplace_back(u); } void remove(){ for(auto &k : added){ int u = findR(edges[k].fi), v = findR(edges[k].se); adj[u].clear(); adj[v].clear(); visited[u] = visited[v] = false; } added.clear(); } int dfs(int u){ visited[u] = true; int ret = sz[u]; for(auto &v : adj[u]){ if(!visited[v]) ret += dfs(v); } return ret; } void Process(int l, int r){ vector<Query> updates, queries; for(int i = l; i <= r; i++){ if(qry[i].type == 1) updates.emplace_back(qry[i]); else queries.emplace_back(qry[i]); } sort(queries.begin(), queries.end(), cmp); sort(eg.begin(), eg.end(), egCmp); //We process from rightmost to leftmost, getting the most updated weight of edge reverse(updates.begin(), updates.end()); for(auto &k : updates) dead[k.a] = true; int id = 0; init(); for(auto &k : queries){ while(id < m && w[eg[id]] >= k.b){ if(!dead[eg[id]]) join(edges[eg[id]].fi, edges[eg[id]].se); id++; } for(auto &ed : updates){ if(ed.idx < k.idx){ if(vis[ed.a]) continue; vis[ed.a] = true; if(ed.b >= k.b) add_edge(ed.a); } } for(auto &ed : updates){ if(ed.idx < k.idx) break; if(!vis[ed.a] && w[ed.a] >= k.b) add_edge(ed.a); } ans[k.idx] = dfs(findR(k.a)); visited[findR(k.a)] = false; for(auto &ed : updates){ vis[ed.a] = false; } remove(); } for(auto &k : updates){ if(!dead[k.a]) continue; dead[k.a] = false; w[k.a] = k.b; } } int main(){ // cerr << sq << "\n"; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ scanf("%d%d%d", &edges[i].fi, &edges[i].se, &w[i]); } scanf("%d", &q); for(int i = 1; i <= q; i++){ scanf("%d%d%d", &qry[i].type, &qry[i].a, &qry[i].b); qry[i].idx = i; } memset(ans, -1, sizeof(ans)); eg.resize(m); iota(eg.begin(), eg.end(), 1); for(int i = 0; i * sq + 1 <= q; i++){ Process(i * sq + 1, min(q, (i + 1) * sq)); } for(int i = 1; i <= q; i++){ if(ans[i] == -1) continue; printf("%d\n", ans[i]); } return 0; }

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

bridges.cpp: In function 'int main()':
bridges.cpp:153:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &edges[i].fi, &edges[i].se, &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &qry[i].type, &qry[i].a, &qry[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...