oj.uz

Submission #238101

# Submission time Handle Problem Language Result Execution time Memory
238101 2020-06-09T23:10:53 Z m3r8 Flood (IOI07_flood) C++14
73 / 100
 233 ms 61596 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];
ii wl[W];
std::vector<int> adj[N];
int zone[N<<2];
int path[N];
std::set<int> sadj[W];
int usedW[W];
int used[N];
int tbl[4] = {2,1,0,3};
int cnt = 1;
int ccnt = 0;
std::queue<ii> que;
std::vector<int> erg;

void cc(int v){
  ccnt = 0;
  que.push({v,0});  
  while(que.size()){
    ii akk = que.front();que.pop();
    used[akk.first] = 1;
    for(auto i: adj[akk.first]){
      if(akk.first == wl[i].first)usedW[ccnt++]=i;  
      if(!used[wl[i].first]){
        que.push({wl[i].first,0});  
      };
      if(!used[wl[i].second]){
        que.push({wl[i].second,0});  
      };
    };
  };
};

void ccp(int ip){
  int p;
  int on;
  int a,b;
  int tprev;
  int tnxt;
  int prev;
  int nxt;
  int idx;
  que.push({ip,0});

  while(que.size()){
    ii akk = que.front();que.pop();
    zone[akk.first] = cnt;
    p = akk.first >> 2;
    on = akk.first % 4;
    tprev = (on+3)%4;
    tnxt = (on+1)%4;
    prev = tprev + (p << 2);
    nxt = tnxt + (p << 2);
    for(auto i: adj[p]){
      idx = wl[i].first;
      if(wl[i].first == p)idx = wl[i].second;
      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(!zone[prev])que.push({prev,0});
    if(!zone[nxt])que.push({nxt,0});
  };
};


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(i);
    adj[b].push_back(i);
    wl[i].first = a;  
    wl[i].second = b;
    if(pp[a] > pp[b]){
      wl[i].first = b;  
      wl[i].second = a;
    };
  };
  int mnid;
  ii mn;
  int prcnt = 1;
  for(int i = 0;i<n;i++){
    if(!used[i]){
      cc(i);
      if(ccnt){
        mn = pp[wl[usedW[0]].first];
        mnid = wl[usedW[0]].first;
        for(int j = 0;j<ccnt;j++){
          int pid = wl[usedW[j]].first;
          if(pp[pid] < mn){
            mn = pp[pid];  
            mnid = pid;
          };
          for(int k = 0;k<4;k++){
            if(!zone[k + (pid << 2)]){
              ccp(k + (pid << 2));
              cnt++;
            };  
          };
          pid = wl[usedW[j]].second;
          if(pp[pid] < mn){
            mn = pp[pid];  
            mnid = pid;
          };
          for(int k = 0;k<4;k++){
            if(!zone[k + (pid << 2)]){
              ccp(k + (pid << 2));
              cnt++;
            };  
          };
        };
        for(int k = 0;k<ccnt;k++){
          int j = usedW[k];
          if(pp[wl[j].second].second - pp[wl[j].first].second == 0){
            sadj[zone[2 + (wl[j].first << 2)]].insert(zone[3 + (wl[j].first << 2)]);
            sadj[zone[3 + (wl[j].first << 2)]].insert(zone[2 + (wl[j].first << 2)]);
            //if(zone[2 + (wl[j].first << 2)] != zone[1 + (wl[j].second << 2)])printf("error\n");
            //if(zone[3 + (wl[j].first << 2)] != zone[0 + (wl[j].second << 2)])printf("error\n");
          }else{
            sadj[zone[1 + (wl[j].first << 2)]].insert(zone[2 + (wl[j].first << 2)]);
            sadj[zone[2 + (wl[j].first << 2)]].insert(zone[1 + (wl[j].first << 2)]);
            //if(zone[1 + (wl[j].first << 2)] != zone[0 + (wl[j].second << 2)])printf("error\n");
            //if(zone[2 + (wl[j].first << 2)] != zone[3 + (wl[j].second << 2)])printf("error\n");
          };
        };
        que.push({zone[(mnid << 2)],1});
        path[zone[(mnid << 2)]] = 1;
        while(que.size()){
          ii akk = que.front();que.pop();  
          for(auto nxt: sadj[akk.first]){
            if(!path[nxt]){
              path[nxt] = akk.second + 1;
              que.push({nxt,akk.second + 1});  
            };
          };
        };
        for(int j = prcnt;j<cnt;j++){
          sadj[j].clear();
        };
        prcnt = cnt;
      };
    };  
  };

  for(int i = 0;i<w;i++){
    if(pp[wl[i].second].second - pp[wl[i].first].second == 0){
      if(path[zone[2 + (wl[i].first << 2)]] == path[zone[3 + (wl[i].first << 2)]]){
        erg.push_back(i+1);
      };
    }else{
      if(path[zone[1 + (wl[i].first << 2)]] == path[zone[2 + (wl[i].first << 2)]]){
        erg.push_back(i+1);
      };
    };
  };
  printf("%d\n",erg.size());
  for(auto i : erg){
    printf("%d\n",i);  
  };
  return 0;
};

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:182:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",erg.size());
                 ~~~~~~~~~~^
flood.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
flood.cpp:87: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:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&w);
   ~~~~~^~~~~~~~~
flood.cpp:93: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 12 ms 12032 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12160 KB Output is correct
2 Correct 16 ms 12544 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 12 ms 12288 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13824 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18164 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 18300 KB Output is correct
2 Runtime error 214 ms 50296 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 209 ms 42720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 233 ms 61596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -