Submission #443484

#TimeUsernameProblemLanguageResultExecution timeMemory
443484urd05Fountain Parks (IOI21_parks)C++17
0 / 100
384 ms31132 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; map<P,int> pt; //점->인덱스 map<P,int> ed; //인덱스쌍->간선인덱스 set<P> vis; vector<P> edge; vector<int> adj[400000]; map<P,P> mp; bool chk[400000]; P ret[400000]; int p[2000]; int find(int a) { return p[a]<0?a:p[a]=find(p[a]); } void merge(int a,int b) { a=find(a); b=find(b); if (a==b) { return; } p[a]+=p[b]; p[b]=a; } int construct_roads(vector<int> x, vector<int> y) { memset(p,-1,sizeof(p)); int n=x.size(); for(int i=0;i<n;i++) { pt[P(x[i],y[i])]=i; } int m=0; for(int i=0;i<n;i++) { if (pt.find(P(x[i]-2,y[i]))!=pt.end()) { int ind=pt[P(x[i]-2,y[i])]; if (ed.find(P(ind,i))!=ed.end()) { ed[P(i,ind)]=ed[P(ind,i)]; } else { ed[P(i,ind)]=m++; edge.push_back(P(i,ind)); } } if (pt.find(P(x[i]+2,y[i]))!=pt.end()) { int ind=pt[P(x[i]+2,y[i])]; if (ed.find(P(ind,i))!=ed.end()) { ed[P(i,ind)]=ed[P(ind,i)]; } else { ed[P(i,ind)]=m++; edge.push_back(P(i,ind)); } } if (pt.find(P(x[i],y[i]-2))!=pt.end()) { int ind=pt[P(x[i],y[i]-2)]; if (ed.find(P(ind,i))!=ed.end()) { ed[P(i,ind)]=ed[P(ind,i)]; } else { ed[P(i,ind)]=m++; edge.push_back(P(i,ind)); } } if (pt.find(P(x[i],y[i]+2))!=pt.end()) { int ind=pt[P(x[i],y[i]+2)]; if (ed.find(P(ind,i))!=ed.end()) { ed[P(i,ind)]=ed[P(ind,i)]; } else { ed[P(i,ind)]=m++; edge.push_back(P(i,ind)); } } } for(int i=0;i<edge.size();i++) { merge(edge[i].first,edge[i].second); } if (-p[find(0)]!=n) { return 0; } for(int i=0;i<edge.size();i++) { if (x[edge[i].first]==x[edge[i].second]) { int nx=x[edge[i].first]-1; int ny=(y[edge[i].first]+y[edge[i].second])/2; if (vis.find(P(nx,ny))==vis.end()) { if (pt.find(P(nx-1,ny+1))!=pt.end()) { int pind=pt[P(nx-1,ny+1)]; int eind=ed[P(pind,pt[P(nx+1,ny+1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else if (pt.find(P(nx-1,ny-1))!=pt.end()) { int pind=pt[P(nx-1,ny-1)]; int eind=ed[P(pind,pt[P(nx+1,ny-1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else { adj[i].push_back(i); mp[P(i,i)]=P(nx,ny); } vis.insert(P(nx,ny)); } nx=x[edge[i].first]+1; if (vis.find(P(nx,ny))==vis.end()) { if (pt.find(P(nx+1,ny+1))!=pt.end()) { int pind=pt[P(nx+1,ny+1)]; int eind=ed[P(pind,pt[P(nx-1,ny+1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else if (pt.find(P(nx+1,ny-1))!=pt.end()) { int pind=pt[P(nx+1,ny-1)]; int eind=ed[P(pind,pt[P(nx-1,ny-1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else { adj[i].push_back(i); mp[P(i,i)]=P(nx,ny); } vis.insert(P(nx,ny)); } } else { int nx=(x[edge[i].first]+x[edge[i].second])/2; int ny=y[edge[i].first]-1; if (vis.find(P(nx,ny))==vis.end()) { if (pt.find(P(nx-1,ny-1))!=pt.end()) { int pind=pt[P(nx-1,ny-1)]; int eind=ed[P(pind,pt[P(nx-1,ny+1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else if (pt.find(P(nx+1,ny-1))!=pt.end()) { int pind=pt[P(nx+1,ny-1)]; int eind=ed[P(pind,pt[P(nx+1,ny+1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else { adj[i].push_back(i); mp[P(i,i)]=P(nx,ny); } vis.insert(P(nx,ny)); } ny=y[edge[i].first]+1; if (vis.find(P(nx,ny))==vis.end()) { if (pt.find(P(nx-1,ny+1))!=pt.end()) { int pind=pt[P(nx-1,ny+1)]; int eind=ed[P(pind,pt[P(nx-1,ny-1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else if (pt.find(P(nx+1,ny+1))!=pt.end()) { int pind=pt[P(nx+1,ny+1)]; int eind=ed[P(pind,pt[P(nx+1,ny-1)])]; adj[eind].push_back(i); adj[i].push_back(eind); mp[P(i,eind)]=P(nx,ny); mp[P(eind,i)]=P(nx,ny); } else { adj[i].push_back(i); mp[P(i,i)]=P(nx,ny); } vis.insert(P(nx,ny)); } } } /*for(int i=0;i<m;i++) { printf("%d\n",adj[i].size()); for(int j=0;j<adj[i].size();j++) { printf("%d ",adj[i][j]); } printf("\n"); }*/ for(int i=0;i<m;i++) { if (chk[i]) { continue; } if (adj[i][0]==i||adj[i][1]==i) { } else { continue; } ret[i]=mp[P(i,i)]; int now; if (adj[i][0]==i) { now=adj[i][1]; } else { now=adj[i][0]; } int prev=i; while (1) { chk[now]=true; if (adj[now][0]==now||adj[now][1]==now) { ret[now]=mp[P(now,now)]; break; } if (adj[now][0]==prev) { ret[now]=mp[P(now,adj[now][1])]; prev=now; now=adj[now][1]; } else { ret[now]=mp[P(now,adj[now][0])]; prev=now; now=adj[now][0]; } } } for(int i=0;i<m;i++) { if (chk[i]) { continue; } ret[i]=mp[P(i,adj[i][0])]; int prev=i; int now=adj[i][0]; chk[i]=true; while (now!=i) { chk[now]=true; if (adj[now][0]==prev) { ret[now]=mp[P(now,adj[now][1])]; prev=now; now=adj[now][1]; } else { ret[now]=mp[P(now,adj[now][0])]; prev=now; now=adj[now][0]; } } } vector<int> uu; vector<int> vv; vector<int> aa; vector<int> bb; for(int i=0;i<m;i++) { uu.push_back(edge[i].first); vv.push_back(edge[i].second); aa.push_back(ret[i].first); bb.push_back(ret[i].second); } build(uu,vv,aa,bb); return 1; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~
parks.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~
#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...