제출 #136754

#제출 시각아이디문제언어결과실행 시간메모리
136754rajarshi_basu다리 (APIO19_bridges)C++14
13 / 100
3031 ms6980 KiB
#include <iostream> #include <vector> #include <set> #include <iomanip> #include <algorithm> #include <functional> #include <stdio.h> #include <cmath> #include <queue> #include <string> #include <map> #include <unordered_map> #include <fstream> #include <complex> #include <random> #include <stack> #include <chrono> #include <set> #define FOR(i,n) for(int i=0;i<n;i++) #define FORE(i,a,b) for(int i=a;i<=b;i++) #define ll long long int #define vi vector<int> #define ii pair<int,int> #define pb push_back #define mp make_pair #define ff first #define ss second #define pll pair<ll,ll> #define cd complex<double> #define ld long double #define pld pair<ld,ld> #define iii pair<ii,int> #define vv vector using namespace std; const int MAXN = 50*1000+1; const int MAXM = 2*MAXN; int n; struct DSU{ struct Oper{ int type; // change in parent = 1, change in rank = 2;checkpoint = 3;size =4 int a; int b; Oper(int t,int aa = 0,int bb = 0){ type = t; a = aa; b = bb; } }; stack<Oper> st; int parent[MAXN]; int sz[MAXN]; int rnk[MAXN]; void init(){ FOR(i,n)parent[i] = i; FOR(i,n)sz[i] = 1; FOR(i,n)rnk[i] = 1; } inline int find(int a){ if(a == parent[a])return a; return find(parent[a]); } inline void merge(int a,int b){ if(isSame(a,b))return; int pa = find(a); int pb = find(b); if(rnk[pa] > rnk[pb]){ st.push(Oper(1,pb)); st.push(Oper(2,pa,sz[pb])); sz[pa] += sz[pb]; parent[pb] = pa; }else if(rnk[pa] < rnk[pb]){ st.push(Oper(1,pa)); st.push(Oper(2,pb,sz[pa])); sz[pb] += sz[pa]; parent[pa] = pb; }else{ st.push(Oper(1,pb)); st.push(Oper(2,pa,sz[pb])); st.push(Oper(4,pa)); sz[pa] += sz[pb]; parent[pb] = pa; rnk[pa]++; } }; int getSize(int a){ return sz[find(a)]; } bool isSame(int a,int b){ return find(a) == find(b); } void setCheckPoint(){ st.push(Oper(3)); } void rollback(){ while(!st.empty()){ auto e = st.top();st.pop(); if(e.type == 3)break; else if(e.type == 1){ parent[e.a] = e.a; }else if(e.type == 2){ sz[e.a] -= e.b; }else{ rnk[e.a]--; } } } }; struct edge{ int ID; int a,b; int w; edge(int id,int aa,int bb,int ww){ ID = id; a = aa; b = bb; w = ww; } }; struct query{ int type; // 1 is update, 2 is query int tm; int info1; // node for query, edge for update int info2; // value for either int id; query(int t,int a,int b,int c){ type = t; tm = id = a; info1 = b; info2 = c; } }; int finalANS[MAXM]; vv<edge> allEdges; vi rem; bool edg[MAXM]; void processQueries(vv<query> allQueries){ FOR(i,MAXM)edg[i] = 0; rem.clear(); for(auto e : allQueries){ if(e.type == 1){ edg[e.info1] = 1; rem.pb(e.info1); } } //cout << "REM CONTENTS : " ; //for(auto e : rem)cout << e << " ";cout << endl; //DSU dsu; //dsu.init(); vv<query> actualQueries; for(auto e : allQueries){ if(e.type == 2){ actualQueries.pb(e); } } vv<edge> nonBlockEdges; FOR(i,allEdges.size()){ if(edg[i])continue; nonBlockEdges.pb(allEdges[i]); } sort(nonBlockEdges.begin(),nonBlockEdges.end(),[&](edge a,edge b){ return a.w > b.w; }); sort(actualQueries.begin(), actualQueries.end(), [&](query a,query b){ return a.info2 > b.info2; }); int PTR = 0; DSU dsu; dsu.init(); for(auto q : actualQueries){ //cout << "PROCESSING FOR QUERY : " << q.info1 << " " << q.info2 << endl; while(PTR < nonBlockEdges.size() and nonBlockEdges[PTR].w >= q.info2){ dsu.merge(nonBlockEdges[PTR].a,nonBlockEdges[PTR].b); PTR++; } dsu.setCheckPoint(); /* FOR(i,allEdges.size()){ if(edg[i])continue; if(allEdges[i].w < q.info2)continue; //cout << "PERMEDGE PROCESSED : " << i+1 << endl; dsu.merge(allEdges[i].a,allEdges[i].b); }*/ unordered_map<int,int> mp; for(auto xx : rem){ mp[xx] = allEdges[xx].w; } for(auto e : allQueries){ if(e.type == 2)continue; if(e.tm > q.tm)continue; //cout << "BLOCK EDGE SEEN : " << e.info1+1 << " " << e.info2 << endl; mp[e.info1] = e.info2; } for(auto x : mp){ if(x.ss >= q.info2){ //cout << "BLOCK EDGE SEEN : " << x.ff+1 << " " << x.ss << endl; dsu.merge(allEdges[x.ff].a,allEdges[x.ff].b); } } finalANS[q.id] = dsu.getSize(q.info1); dsu.rollback(); } for(auto e : allQueries){ if(e.type == 1){ allEdges[e.info1].w = e.info2; } } } bool quer[MAXM]; #define endl '\n' int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m; cin >> n >> m; FOR(i,m){ int a,b,c; cin >> a >> b >> c; a--;b--; allEdges.pb(edge(i,a,b,c)); } int q; cin >> q; FOR(i,MAXM)finalANS[i] = -1; int BLOCK = 300; vv<query> allq; FOR(i,q){ int a,b,c; cin >> a >> b >> c; if(a == 2)quer[i] = 1; b--; allq.pb(query(a,i,b,c)); if((i+1)%BLOCK == 0){ processQueries(allq); allq.clear(); } } if(allq.size() > 0)processQueries(allq); FOR(i,q){ if(finalANS[i] == -1 and quer[i])while(1); if(quer[i])cout << finalANS[i] << endl; } return 0; }

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

bridges.cpp: In function 'void processQueries(std::vector<query>)':
bridges.cpp:20:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     #define FOR(i,n) for(int i=0;i<n;i++)
bridges.cpp:169:10:
      FOR(i,allEdges.size()){
          ~~~~~~~~~~~~~~~~~         
bridges.cpp:169:6: note: in expansion of macro 'FOR'
      FOR(i,allEdges.size()){
      ^~~
bridges.cpp:185:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(PTR < nonBlockEdges.size() and nonBlockEdges[PTR].w >= q.info2){
             ~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...