제출 #555675

#제출 시각아이디문제언어결과실행 시간메모리
555675shahriarkhan다리 (APIO19_bridges)C++14
0 / 100
3054 ms7196 KiB
#include<bits/stdc++.h> using namespace std ; const int MX = 1e5 + 5 , block = 320 ; struct query { int type = 0 , vertice = 0 , edge = 0 , weight = 0 , idx = 0 ; }; bool cmp(pair<int,int> &a , pair<int,int> &b) { if(a.first!=b.first) return a.first > b.first ; return a.second > b.second ; } bool cmp1(query &a , query &b) { if(a.weight!=b.weight) return a.weight > b.weight ; return a.idx < b.idx ; } vector<query> temp ; vector<pair<int,int> > edges ; int ans[MX] , typ[MX] , val[MX] , temp_siz , n , m ; struct dsu_rollback { int u = 0 , v = 0 , siz_u = 0 , siz_v = 0 ; }; struct dsu { vector<int> par , siz ; stack<dsu_rollback> s ; void init(int n) { par = vector<int> (n+5,0) ; siz = vector<int> (n+5,0) ; for(int i = 1 ; i <= n ; ++i) { par[i] = i ; siz[i] = 1 ; } } int find_root(int a) { if(par[a]==a) return a ; return find_root(par[a]) ; } void union_edge(int a , int b) { int root_a = find_root(a) , root_b = find_root(b) ; if(root_a==root_b) return ; if(siz[root_b]>siz[root_a]) swap(root_a,root_b) ; s.push({root_a,root_b,siz[root_a],siz[root_b]}) ; par[root_b] = root_a ; siz[root_a] += siz[root_b] ; return ; } void rollback() { if(s.empty()) return ; dsu_rollback cur = s.top() ; par[cur.u] = cur.u ; siz[cur.u] = cur.siz_u ; par[cur.v] = cur.v ; siz[cur.v] = cur.siz_v ; } int find_siz(int x) { return siz[find_root(x)] ; } }; void process() { dsu D ; D.init(n) ; int vis[m+2] = {0} , cur[m+2] = {0} ; vector<query> upd , out ; vector<int> unused ; for(query q : temp) { if(q.type==1) { vis[q.edge] = 1 ; upd.push_back(q) ; } else out.push_back(q) ; } vector<pair<int,int> > edg ; for(int i = 1 ; i <= m ; ++i) { if(!vis[i]) edg.push_back({val[i],i}) ; else unused.push_back(i) ; } sort(edg.begin(),edg.end(),cmp) ; sort(out.begin(),out.end(),cmp1) ; int edg_siz = edg.size() , cr = 0 ; for(query q : out) { while((cr<edg_siz) && (edg[cr].first>=q.weight)) { D.union_edge(edges[edg[cr].second].first,edges[edg[cr].second].second) ; ++cr ; } int rollback = 0 ; for(query p : upd) { if(p.idx>q.idx) break ; cur[p.edge] = p.weight ; } for(query p : upd) { if(p.idx>q.idx) break ; if(cur[p.edge]>=q.weight) { D.union_edge(edges[p.edge].first,edges[p.edge].second) ; ++rollback , cur[p.edge] = -1 ; } } for(int i : unused) { if(cur[i]) continue ; if(val[i]>=q.weight) { D.union_edge(edges[i].first,edges[i].second) ; ++rollback , cur[i] = -1 ; } } ans[q.idx] = D.find_siz(q.vertice) ; while(rollback) { D.rollback() ; --rollback ; } for(int i : unused) { cur[i] = 0 ; } } for(query q : upd) { val[q.edge] = q.weight ; } for(int i : unused) { vis[i] = 0 ; } temp.clear() , temp_siz = 0 ; } int main() { scanf("%d%d",&n,&m) ; edges.push_back({0,0}) ; for(int i = 1 ; i <= m ; ++i) { int a , b , d ; scanf("%d%d%d",&a,&b,&d) ; edges.push_back({a,b}) ; val[i] = d ; } int q ; scanf("%d",&q) ; for(int i = 1 ; i <= q ; ++i) { int type ; scanf("%d",&type) ; typ[i] = type ; if(type==1) { int b , r ; scanf("%d%d",&b,&r) ; temp.push_back({1,0,b,r,i}) , ++temp_siz ; } else { int s , w ; scanf("%d%d",&s,&w) ; temp.push_back({2,s,0,w,i}) , ++temp_siz ; } if(temp_siz==block) process() ; } if(temp_siz) process() ; for(int i = 1 ; i <= q ; ++i) { if(typ[i]==2) printf("%d\n",ans[i]) ; } return 0 ; }

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

bridges.cpp: In function 'int main()':
bridges.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     scanf("%d%d",&n,&m) ;
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         scanf("%d%d%d",&a,&b,&d) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |     scanf("%d",&q) ;
      |     ~~~~~^~~~~~~~~
bridges.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         scanf("%d",&type) ;
      |         ~~~~~^~~~~~~~~~~~
bridges.cpp:177:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |             scanf("%d%d",&b,&r) ;
      |             ~~~~~^~~~~~~~~~~~~~
bridges.cpp:183:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |             scanf("%d%d",&s,&w) ;
      |             ~~~~~^~~~~~~~~~~~~~
#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...