oj.uz

Submission #133997

# Submission time Handle Problem Language Result Execution time Memory
133997 2019-07-21T22:28:33 Z dragonslayerit Flood (IOI07_flood) C++14
54 / 100
 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

flood.cpp: In function 'int main()':
flood.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<adj[i].size();j++){
                 ~^~~~~~~~~~~~~~
flood.cpp:85:9: warning: unused variable 'a' [-Wunused-variable]
     int a=elist[i],b=elist[i^1];
         ^
flood.cpp:85:20: warning: unused variable 'b' [-Wunused-variable]
     int a=elist[i],b=elist[i^1];
                    ^
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:59: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:18: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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19960 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19832 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19960 KB Output is correct
2 Correct 22 ms 19936 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory 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 -

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19960 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19932 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19960 KB Output is correct
2 Correct 26 ms 20008 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19960 KB Output is correct
2 Correct 21 ms 19980 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 45944 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 31676 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory 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)

Subtask #13
0 / 9.0

# Verdict Execution time Memory 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 -

Subtask #14
0 / 9.0

# Verdict Execution time Memory 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 -