Submission #289606

#TimeUsernameProblemLanguageResultExecution timeMemory
289606DoxenoFlood (IOI07_flood)C++17
0 / 100
2085 ms12928 KiB
#include <bits/stdc++.h> using namespace std; int uf[400000]; int siz[400000]; bool vis[400000],pres[400000]; int tim[400000]; bool sos[400000]; void in(int &n) { n = 0; int c = getc_unlocked(stdin), m = 0; for (; c < '0' || c > '9'; c = getc_unlocked(stdin)) if (c == '-') m = 1; for (; c >= '0' && c <= '9'; c = getc_unlocked(stdin)) n = (n << 1) + (n << 3) + c - '0'; if (m) n = -n; } void out(int n) { if (!n) putc_unlocked('0', stdout); int c[11], i = 0; if (n < 0) { putc_unlocked('-', stdout); n = -n; } for (; n; n /= 10, i++) c[i] = n % 10 + '0'; for (i--; i >= 0; putc_unlocked(c[i], stdout), i--); putc_unlocked('\n', stdout); } vector<pair<int,int>> adjj[400000]; int find(int a){ if(uf[a]!=a)uf[a]=find(uf[a]); return uf[a]; } void uni(int a,int b){ a = find(a); b = find(b); if(siz[a]>siz[b])swap(a,b); uf[a]=b; siz[b]+=siz[a]; } int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int N,K,a,b; for(int i = 0; i < 400000; i++){siz[i]=1;uf[i]=i;} in(N); int cx[N]; int cy[N]; int curr = N-1; vector<pair<int,int>> adj[N]; for(int i = 0; i < N; i++){in(cx[i]);in(cy[i]);} in(K); vector<pair<int,int>> pts; for(int i = 0; i < N; i++)pts.push_back({cy[i],i}); sort(pts.begin(),pts.end()); int walls[K][2],arcs[K][2]; for(int i = 0; i < K; i++){ in(a); in(b); adj[a-1].push_back({b-1,i}); adj[b-1].push_back({a-1,i}); arcs[i][1]=a-1; arcs[i][0]=b-1; } int sas[4]; int x,y; for(int i = 0; i < N; i++){ sas[0]=-1;sas[1]=-1;sas[2]=-1;sas[3]=-1; for(auto k: adj[i]){ x=k.first; y=k.second; if(cx[x]==cx[i]){ if(cy[x]>cy[i]){sas[0]=x;walls[y][0]=i;walls[y][1]=i+100000;} else sas[2]=x; }else{ if(cx[x]>cx[i]){sas[1]=x;walls[y][0]=i+100000;walls[y][1]=i+200000;} else sas[3]=x; } } if(sas[0]==-1){uni(i,i+100000);} else{uni(i,sas[0]+300000); uni (i+100000,sas[0]+200000);} if(sas[1]==-1){uni(i+100000,i+200000);} else{uni(i+100000,sas[1]);uni(i+200000, sas[1]+300000);} if(sas[2]==-1){uni(i+200000,i+300000);} else{uni(i+300000,sas[2]);uni(i+200000,sas[2]+100000);} if(sas[3]==-1){uni(i,i+300000);} else{uni(i,100000+sas[3]);uni(i+300000,sas[3]+200000);} } //for(int i = 0; i < 4; ,res=K;i++){cout << find(i*100000+1) << " " << find(i*100000) << "\n";} for(int i = 0;i < K;i++){ a=find(walls[i][0]); b=find(walls[i][1]); adjj[a].push_back({b,i}); adjj[b].push_back({a,i}); } for(int i = 0; i < 400000; i++){vis[i]=0; pres[i]=0;tim[i]=-1;sos[i]=0;} queue <pair<int,int>> q; int t,node; bool sus = true; do{ if(q.empty()){ while(sos[pts[curr].second] && curr >= 0)curr--; if(curr < 0){sus=false;break;} tim[find(pts[curr].second)]=t; q.push({find(pts[curr--].second),t}); } node = q.front().first; t = q.front().second; q.pop(); //cout << node<< "\n"; vis[node]=1; //cout<< "node " << node << "\n"; for(auto x: adjj[node]){ sos[arcs[x.second][0]]=1; sos[arcs[x.second][1]]=1; if(tim[x.first]==-1){ q.push({x.first,t+1}); tim[x.first]=t+1; //cout<<x.second<<endl; } } }while(sus); vector <int> res; for(int i = 0; i < K; i++){ if(tim[find(walls[i][0])]==tim[find(walls[i][1])])res.push_back(i+1); } out(res.size()); for(auto x: res)out(x); return 0; }

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  freopen("input.txt","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  freopen("output.txt","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:97:40: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |             tim[find(pts[curr].second)]=t;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...