# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
133997 | 2019-07-21T22:28:33 Z | dragonslayerit | Flood (IOI07_flood) | C++14 | 348 ms | 45944 KB |
#include <cstdio> #include <tuple> #include <vector> #include <algorithm> #include <queue> #include <cmath> #include <cassert> const int INF=1e9+7; struct Point{ int x,y; Point():x(0),y(0){ } Point(int x,int y):x(x),y(y){ } void read(){ scanf("%d %d",&x,&y); } bool operator<(Point p)const{ return std::tie(y,x)<std::tie(p.y,p.x); } Point operator-(Point p)const{ return Point(x-p.x,y-p.y); } double arg()const{ return std::atan2(y,x); } }ps[100005]; int elist[400005]; std::vector<int> adj[400005]; std::vector<int> dual[400005]; int cc[400005]; int cc_cnt=0; int dist[400005]; void dfs_cc(int x,int color){ if(cc[x]!=-1) return; cc[x]=color; for(int y:dual[x]){ dfs_cc(y,color); } } int main(){ int N; scanf("%d",&N); for(int i=0;i<N;i++){ ps[i].read(); } int W; scanf("%d",&W); std::fill(cc,cc+W*2,-1); for(int i=0;i<W;i++){ int A,B; scanf("%d %d",&A,&B); A--,B--; elist[i*2]=A; elist[i*2+1]=B; adj[A].push_back(i*2+1); adj[B].push_back(i*2); } for(int i=0;i<N;i++){ std::sort(adj[i].begin(),adj[i].end(),[i](int x,int y){ return (ps[elist[x]]-ps[i]).arg()< (ps[elist[y]]-ps[i]).arg();}); for(int j=0;j<adj[i].size();j++){ int k=(j+1)%adj[i].size(); dual[adj[i][j]].push_back(adj[i][k]^1); } } for(int i=0;i<W*2;i++){ if(cc[i]==-1){ dfs_cc(i,cc_cnt++); } } for(int i=0;i<W*2;i++){ dual[i].clear(); } //printf("DUAL: %d vertices\n",cc_cnt); for(int i=0;i<W*2;i++){ int a=elist[i],b=elist[i^1]; //printf("%d => %d: %d => %d\n",a+1,b+1,cc[i],cc[i^1]); dual[cc[i]].push_back(cc[i^1]); } std::vector<int> is; for(int i=0;i<N;i++){ is.push_back(i); } std::sort(is.begin(),is.end(),[](int i,int j){return ps[i]<ps[j];}); std::queue<int> q; std::fill(dist,dist+N,INF); for(int i:is){ int root=cc[adj[i][0]^1]; if(dist[root]!=INF) continue; //printf("Root=%d\n",root); q.push(root); dist[root]=0; while(!q.empty()){ int x=q.front(); q.pop(); for(int y:dual[x]){ if(dist[y]==INF){ dist[y]=dist[x]+1; q.push(y); } } } } std::vector<int> survive; for(int i=0;i<W;i++){ int a=cc[i*2],b=cc[i*2+1]; assert(dist[a]!=-1); assert(dist[b]!=-1); if(dist[a]==dist[b]){ survive.push_back(i+1); } } printf("%d\n",(int)survive.size()); for(int wall:survive){ printf("%d\n",wall); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19960 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19960 KB | Output is correct |
2 | Correct | 19 ms | 19960 KB | Output is correct |
3 | Correct | 20 ms | 19960 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19832 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 19960 KB | Output is correct |
2 | Correct | 22 ms | 19936 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 46 ms | 40144 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 19960 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 19932 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 19960 KB | Output is correct |
2 | Correct | 26 ms | 20008 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 19960 KB | Output is correct |
2 | Correct | 21 ms | 19980 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 71 ms | 45944 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 117 ms | 31676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 117 ms | 30576 KB | Output is correct |
2 | Runtime error | 348 ms | 39828 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 301 ms | 35528 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 326 ms | 37104 KB | Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
2 | Halted | 0 ms | 0 KB | - |