답안 #134476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134476	2019-07-22T18:55:08 Z	dragonslayerit	Flood (IOI07_flood)	C++14	81 / 100	266 ms	29168 KB

flood

#include <cstdio>
#include <tuple>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cassert>
     
const int INF=1e9+7;

const double PI=4*atan(1);
     
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{
    double res=std::atan2(y,x);
    if(res<0) res+=2*PI;
    return res;
  }
}ps[100005];
     
int elist[400005];
     
std::vector<int> adj[400005];
int next[400005];
std::vector<int> dual[100005];
int* cc=elist;
int cc_cnt=0;
     
int dist[100005];
     
int q[100005];
int qh=0,qt=0;
     
int main(){
  int N;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    ps[i].read();
  }
  int W;
  scanf("%d",&W);
  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();
      next[adj[i][j]]=adj[i][k]^1;
    }
  }
  //elist expires
  //cc begins
  std::fill(cc,cc+W*2,-1);
  for(int i=0;i<W*2;i++){
    if(cc[i]==-1){
      for(int x=i;cc[x]==-1;x=next[x]){
    	cc[x]=cc_cnt;
      }
      cc_cnt++;
    }
  }
  //printf("DUAL: %d vertices\n",cc_cnt);
  for(int i=0;i<W*2;i++){
    //printf("%d => %d: %d => %d\n",a+1,b+1,cc[i],cc[i^1]);
    dual[cc[i]].push_back(cc[i^1]);
  }
  for(int i=0;i<N;i++){
    ps[i].x=i;
  }
  std::sort(ps,ps+N);
  //std::queue<int> q;
  std::fill(dist,dist+N,INF);
  for(int i=0;i<N;i++){
    int root=cc[adj[ps[i].x][0]^1];
    if(dist[root]!=INF) continue;
    //printf("Root=%d\n",root);
    q[qh++]=root;
    //q.push(root);
    dist[root]=0;
    // while(!q.empty()){
    while(qh!=qt){
      int x=q[qt++];//q.front();
      //q.pop();
      for(int y:dual[x]){
    	if(dist[y]==INF){
    	  dist[y]=dist[x]+1;
    	  //q.push(y);
    	  q[qh++]=y;
    	}
      }
    }
  }
  int survive=0;
  for(int i=0;i<W;i++){
    if(dist[cc[i*2]]==dist[cc[i*2+1]]){
      survive++;
    }
  }
  printf("%d\n",survive);
  for(int i=0;i<W;i++){
    if(dist[cc[i*2]]==dist[cc[i*2+1]]){
      printf("%d\n",i+1);
    }
  }
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<adj[i].size();j++){
                 ~^~~~~~~~~~~~~~
flood.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~
flood.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&W);
   ~~~~~^~~~~~~~~
flood.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&A,&B);
     ~~~~~^~~~~~~~~~~~~~~
flood.cpp: In member function 'void Point::read()':
flood.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&x,&y);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12792 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12792 KB	Output is correct
2	Correct	16 ms	12844 KB	Output is correct
3	Correct	17 ms	12920 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12792 KB	Output is correct

Subtask #4

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12792 KB	Output is correct
2	Correct	16 ms	12920 KB	Output is correct

Subtask #5

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	37 ms	25848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #6

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12920 KB	Output is correct

Subtask #7

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12920 KB	Output is correct

Subtask #8

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12920 KB	Output is correct
2	Correct	13 ms	12920 KB	Output is correct

Subtask #9

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12920 KB	Output is correct
2	Correct	14 ms	12920 KB	Output is correct

Subtask #10

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	59 ms	29168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #11

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	20216 KB	Output is correct

Subtask #12

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	21280 KB	Output is correct
2	Correct	266 ms	24412 KB	Output is correct

Subtask #13

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	190 ms	23160 KB	Output is correct
2	Correct	230 ms	25080 KB	Output is correct

Subtask #14

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	216 ms	24184 KB	Output is correct
2	Correct	145 ms	21848 KB	Output is correct