oj.uz

Submission #238258

# Submission time Handle Problem Language Result Execution time Memory
238258 2020-06-10T14:22:46 Z m3r8 Flood (IOI07_flood) C++14
100 / 100
 258 ms 13164 KB 
#include <stdio.h>
#include <set>
#include <utility>
#include <vector>
#include <queue>

#define N 100100
#define W N*2
#define ii std::pair<int,int>

ii pp[N];
std::vector<ii> adj[N];
int zone[N<<2];
int used[N];
int tbl[4] = {2,1,0,3};
std::queue<int> que;
int erg[W];
std::vector<int> akt;
std::vector<int> ttmp;

void cc(int v){
  que.push(v);  
  used[v] = 1;
  while(que.size()){
    int akk = que.front();que.pop();
    akt.push_back(akk);
    for(auto i: adj[akk]){
      if(!used[i.first]){
        used[i.first] = 1;
        que.push(i.first);  
      };
    };
  };
};

void ccp(int sp){
  int ip = sp << 2;
  int cnt = 1;
  int p;
  int on;
  int a,b;
  int tprev;
  int tnxt;
  int prev;
  int nxt;
  int idx;
  que.push(ip);
  zone[ip] = cnt;
  while(que.size()){
    while(que.size()){
      int akk = que.front();que.pop();
      p = akk >> 2;
      on = akk % 4;
      //printf("on: %d %d %d %d\n",p,on,pp[p].first,pp[p].second);
      tprev = (on+3)%4;
      tnxt = (on+1)%4;
      prev = tprev + (p << 2);
      nxt = tnxt + (p << 2);
      for(auto i: adj[p]){
        idx = i.first;
        a = pp[idx].first - pp[p].first == 0;
        if(a)b = pp[idx].second - pp[p].second < 0;
        else b = pp[idx].first - pp[p].first < 0;
        a = b * 2 + a;
        if(tbl[on] == a){
          nxt = tprev + (idx << 2);  
        };
        if((tbl[on] + 1)%4 == a){
          prev = tnxt + (idx << 2);  
        };
      };
      if(p == 208){
        //printf("nn: %d %d %d %d %d %d %d\n",prev>>2,nxt>>2,zone[prev],zone[nxt],zone[akk],prev%4,on);  
      };
      if(!zone[prev]){
        zone[prev] = cnt;
        que.push(prev);  
      };
      if(!zone[nxt]){
        zone[nxt] = cnt;
        que.push(nxt);  
      };
      ttmp.push_back(tprev + (p << 2));  
      ttmp.push_back(tnxt + (p << 2));  
    };
    //printf("---------------\n");
    cnt++;
    for(int i: ttmp){
      if(!zone[i]){
        que.push(i); 
        zone[i] = cnt;
      }; 
    };
    ttmp.clear();
  };
};


int main(void){
  int n;
  scanf("%d",&n);
  for(int i = 0;i<n;i++){
    scanf("%d %d",&(pp[i].first),&(pp[i].second));  
  };
  int w;
  scanf("%d",&w);
  int a,b;
  for(int i = 0;i<w;i++){
    scanf("%d %d",&a,&b);
    a--;
    b--;
    adj[a].push_back({b,i});
    adj[b].push_back({a,i});
  };
  int mnid;
  ii mn;
  for(int i = 0;i<n;i++){
    if(!used[i]){
      akt.clear();
      cc(i);
      if(akt.size() > 1){
        mn = pp[akt[0]];
        mnid = akt[0];
        for(int j : akt){
          if(pp[j] < mn){
            mn = pp[j];  
            mnid = j;
          };
        };
        ccp(mnid);
      };
    };  
  };

  ii aa,bb;
  for(int i = 0;i<n;i++){
    for(auto j: adj[i]){
      aa = pp[i];
      bb = pp[j.first];
      if(aa.first == bb.first){
        if(aa.second < bb.second){
          if(zone[1 + (i << 2)] == zone[2 + (i << 2)]){
            erg[j.second] = 1;
          };
        }else{
          if(zone[1 + (j.first << 2)] == zone[2 + (j.first << 2)]){
            erg[j.second] = 1;
          };
        };  
      }else{
        if(aa.first < bb.first){
          if(zone[2 + (i << 2)] == zone[3 + (i << 2)]){
            erg[j.second] = 1;
          };
        }else{
          if(zone[2 + (j.first << 2)] == zone[3 + (j.first << 2)]){
            erg[j.second] = 1;
          };
        }; 
      };
    };  
  };
  int cccc = 0;
  for(int i = 0;i<w;i++){
    if(erg[i])cccc++;  
  };
  printf("%d\n",cccc);
  for(int i = 0;i<w;i++){
    if(erg[i])printf("%d\n",i+1);
  };
  return 0;
};

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
flood.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&(pp[i].first),&(pp[i].second));  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&w);
   ~~~~~^~~~~~~~~
flood.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&a,&b);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4224 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8720 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 7928 KB Output is correct
2 Correct 206 ms 11948 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 11008 KB Output is correct
2 Correct 192 ms 12268 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 11544 KB Output is correct
2 Correct 145 ms 13164 KB Output is correct