oj.uz

Submission #238079

# Submission time Handle Problem Language Result Execution time Memory
238079 2020-06-09T21:51:36 Z m3r8 Flood (IOI07_flood) C++14
82 / 100
 301 ms 44692 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<ii> adj[N];
unsigned short zone[N<<2];
unsigned short path[N];
std::set<unsigned short> sadj[W];
std::vector<int> akt;
std::vector<int> akt2;
bool used[N];
int tbl[4] = {2,1,0,3};

void cc(int v){
  used[v] = 1;
  akt.push_back(v);
  for(auto i: adj[v]){
    if(wl[i.second].first == v)akt2.push_back(i.second);
    if(!used[i.first]){
      cc(i.first);
    };  
  };
};
int cnt = 1;

void ccp(int ip){
  zone[ip] = cnt;
  int p = ip >> 2;
  int on = ip % 4;
  int a,b;
  int tprev = (on+3)%4;
  int tnxt = (on+1)%4;
  int prev = tprev + (p << 2);
  int nxt = tnxt + (p << 2);

  for(auto i: adj[p]){
    a = pp[i.first].first - pp[p].first == 0;
    if(a)b = pp[i.first].second - pp[p].second < 0;
    else b = pp[i.first].first - pp[p].first < 0;
    a = b * 2 + a;
    //printf("%d\n",a);
    if(tbl[on] == a){
      nxt = tprev + (i.first << 2);  
    };
    if((tbl[on] + 1)%4 == a){
      prev = tnxt + (i.first << 2);  
    };
  };
  //printf("%d go from %d %d to %d %d and %d %d prev: %d  nxt: %d cnt: %d\n",ip,pp[p].first,pp[p].second,pp[prev >> 2].first,pp[prev >> 2].second,pp[nxt >> 2].first,pp[nxt >> 2].second,prev,nxt,cnt);

  if(!zone[prev])ccp(prev);
  if(!zone[nxt])ccp(nxt);

};

std::queue<ii> que;
std::vector<int> erg;

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});
    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]){
      akt.clear();
      akt2.clear();
      cc(i);
      if(akt.size() > 1){
        mn = pp[akt[0]];
        mnid = akt[0];
        for(auto j: akt){
          if(pp[j] < mn){
            mn = pp[j];  
            mnid = j;
          };
          for(int k = 0;k<4;k++){
            if(!zone[k + (j << 2)]){
              ccp(k + (j << 2));
              cnt++;
            };  
          };
        };
        for(auto j: akt2){
          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:155: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
flood.cpp:71: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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&w);
   ~~~~~^~~~~~~~~
flood.cpp:77: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 11 ms 12032 KB Output is correct

Subtask #2
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
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 12032 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12136 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 12 ms 12032 KB Output is correct
2 Correct 11 ms 12160 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 12 ms 12160 KB Output is correct

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 13560 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 22388 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 17272 KB Output is correct
2 Correct 255 ms 30816 KB Output is correct

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 24944 KB Output is correct
2 Runtime error 257 ms 36388 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 31788 KB Output is correct
2 Runtime error 219 ms 44692 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)