oj.uz

답안 #238055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
238055 2020-06-09T20:28:04 Z m3r8 Flood (IOI07_flood) C++14
46 / 100
 222 ms 33056 KB 
#include <stdio.h>
#include <set>
#include <utility>
#include <vector>
#include <queue>

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

ii pp[N];
ii wl[W];
std::vector<ii> adj[N];
int zone[N<<2];
int path[N<<2];
std::set<int> sadj[W];
int kill[W];
std::vector<int> akt;
std::vector<int> akt2;
int 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(!used[i.first]){
      akt2.push_back(i.second);
      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;
  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)]);
          }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)]);
          };
        };
        que.push({zone[(mnid << 2)],1});
        while(que.size()){
          ii akk = que.front();que.pop();  
          path[akk.first] = akk.second; 
          for(auto nxt: sadj[akk.first]){
            if(!path[nxt]){
              path[nxt] = akk.second + 1;
              que.push({nxt,akk.second + 1});  
            };
          };
        };
      };
    };  
  };

  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:147: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:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
flood.cpp:72: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:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&w);
   ~~~~~^~~~~~~~~
flood.cpp:78: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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Incorrect 12 ms 12164 KB Output isn't correct

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 14456 KB Output isn't correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 26232 KB Output isn't correct

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 22648 KB Output is correct
2 Incorrect 210 ms 32576 KB Output isn't correct

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 177 ms 29428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 222 ms 33056 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -