oj.uz

답안 #1020117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020117 2024-07-11T15:12:59 Z anton 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 4000 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;


int nbCycles = 0;
int szCycle= 0;

struct DSU{
  int nbGroups =0;
  vector<int> anc;
  vector<int> sz;
  vector<pair<int, pair<int, int>>> op_buffer;

  DSU(){};
  DSU(int l){
    anc.resize(l);
    sz.resize(l);
    for(int i = 0; i<l; i++){
      anc[i] = i;
      sz[i] = 1;
    }
    nbGroups = l;
  }
  int c(int u){
    op_buffer.push_back({u, {anc[u], sz[u]}});
    if(anc[u] == u){
      return u;
    }
    int v= c(anc[u]);
    anc[u] =v;
    return v;
  }

  void merge(int a, int b){
    //cerr<<"merging "<<a<<" "<<b<<endl;
    a = c(a);
    b= c(b);
    if(a==b){
      nbCycles ++;
      szCycle = sz[a];
      return;
    }
    nbGroups--;

    op_buffer.push_back({a, {anc[a], sz[a]}});
    op_buffer.push_back({b, {anc[b], sz[b]}});

    if(sz[a]>sz[b]){
      swap(a, b);
    }

    anc[a] = b;
    sz[b] += sz[a];  
  }

  void undo_buffer(){
    while(op_buffer.size()>0){
      auto e= op_buffer.back();
      if(anc[e.first] == e.first){
        nbGroups--;
      }
      op_buffer.pop_back();
      anc[e.first] = e.second.first;
      sz[e.first] = e.second.second;
      if(anc[e.first] == e.first){
        nbGroups++;
      }
    }
  }
};

int N;
const int MAX_N= 1e6;
vector<int> adj[MAX_N];
vector<int> interesting;
bool isInteresting[MAX_N];
int deg[MAX_N], oc[MAX_N];

DSU curDSU;
int above3= 0;
int above4 = 0;


DSU recalcDSU(){
  DSU newDSU(N);
  for(int iV = 0; iV<N; iV++){
    
      for(auto u: adj[iV]){
        if(!(isInteresting[u] || isInteresting[iV])){
          newDSU.merge(iV, u);
        }
      }
    
  }

  newDSU.op_buffer.clear();
  return newDSU;
}

bool lost3 = false;

int count3(int u){
  int res= 0;
  for(auto e: adj[u]){
    if(deg[e]>=3){
      res++;
    }
  }
  return res;
}
void changeDeg(int u, int d){
  
  if(deg[u]>=3){
    above3--;
  }
  if(deg[u] >= 4){
    above4--;
  }
  oc[deg[u]]--;
  deg[u] +=d;
  oc[deg[u]] ++;
  if(deg[u]>=3){
    above3++;
  }
  if(deg[u] >= 4){
    above4++;
  }
}


void Init(int N_) {

  
  N = N_;
  fill(&oc[0], &oc[N], 0);
  oc[0]  =N;

  curDSU = DSU(N);

}

bool check_possible(){

  if(interesting.size() == 0){
    return true;
  }
  unordered_map<int, int> m;
  int target = 0;

  for(auto e: interesting){
    if(deg[e] == 3){
    
      for(auto ee: adj[e]){
        m[ee]++;
      }
      m[e]++;
      target++;

    }
  }

  for(auto e: m){
    if(e.second == target){
      return true;
    }
  }
  return false;

  
}

void Link(int A, int B) {
  if(above4>1 || lost3){
    return;
  }

  adj[A].push_back(B);
  changeDeg(A, +1);
  adj[B].push_back(A);
  changeDeg(B, +1);
  if(deg[A]== 3 || deg[B]==3){

    if(deg[A] != 3){
      swap(A, B);
    }
    if(!isInteresting[A]){
      isInteresting[A] = true;
      interesting.push_back(A);
    }
    for(auto e: adj[A]){
      if(!isInteresting[e]){
        isInteresting[e] = true;
        interesting.push_back(e);
      }
    }
    if(deg[B] == 3){
      if(!isInteresting[B]){
        isInteresting[B] = true;
        interesting.push_back(B);
      }
      for(auto e: adj[B]){
        if(!isInteresting[e]){
          isInteresting[e] = true;
          interesting.push_back(e);
        }
      }
    }
    curDSU = recalcDSU();
  }
  else if(isInteresting[A] || isInteresting[B]){

  }
  else{
    curDSU.merge(A, B);
    curDSU.op_buffer.clear();
  }

  if(deg[A]>=4){
    if(count3(A)<above3-1){
      lost3 = true;
    }
  }
  if(deg[B]>=4){
    if(count3(B)<above3-1){
      lost3 = true;
    }
  }

  if(above4 == 0){
    if(!check_possible()){
      lost3 = true;
    }
  }
}

int CountCritical() {
  if(above4>1 || lost3){
    return 0;
  }
  else{
    if(above3>=1){
      int res= 0;


      for(auto iAdd: interesting){
        for(auto e: adj[iAdd]){
          if(!isInteresting[e]){
            changeDeg(e, -1);
          }
          changeDeg(iAdd, -1);
        }
      }


      for(auto iRem: interesting){
        if(deg[iRem]>=4 || above4 ==0){
          for(auto iAdd: interesting){
            if(iAdd!=iRem){
              for(auto e: adj[iAdd]){
                if(e!=iRem){
                  curDSU.merge(e, iAdd);
                  if(!isInteresting[e]){
                    changeDeg(e, 1);
                  }
                  changeDeg(iAdd, 1);
                }
              }
            }
          }

          
          if((oc[0]-1)*2 + oc[1] == (curDSU.nbGroups-1)*2 && above3 ==0){
            res++;
          }


          for(auto iAdd: interesting){
            if(iAdd!=iRem){
              for(auto e: adj[iAdd]){
                if(e!=iRem){
                  if(!isInteresting[e]){
                    changeDeg(e, -1);
                  }
                  changeDeg(iAdd, -1);
                }
              }
            }
          }
          curDSU.undo_buffer();
        }
      }


      for(auto iAdd: interesting){
        for(auto e: adj[iAdd]){
          if(!isInteresting[e]){
            changeDeg(e, 1);
          }
          changeDeg(iAdd, 1);
        }
      }
      return res;
    }
    else{
      if(nbCycles == 0){
        return N;
      }
      else if(nbCycles == 1){
        return szCycle;
      }
      else{
        return 0;
      }
    }
  }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 14 ms 24412 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 10 ms 24156 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 13 ms 24804 KB Output is correct
10 Correct 13 ms 25176 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 48360 KB Output is correct
2 Correct 613 ms 84496 KB Output is correct
3 Correct 150 ms 49732 KB Output is correct
4 Correct 669 ms 70976 KB Output is correct
5 Correct 743 ms 70752 KB Output is correct
6 Correct 630 ms 69716 KB Output is correct
7 Correct 150 ms 51024 KB Output is correct
8 Correct 1141 ms 232464 KB Output is correct
9 Correct 1399 ms 262144 KB Output is correct
10 Correct 424 ms 68944 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 14 ms 24412 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 10 ms 24156 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 13 ms 24804 KB Output is correct
10 Correct 13 ms 25176 KB Output is correct
11 Correct 16 ms 25844 KB Output is correct
12 Correct 19 ms 28244 KB Output is correct
13 Correct 62 ms 29156 KB Output is correct
14 Execution timed out 4067 ms 25860 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 14 ms 24412 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 10 ms 24156 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 13 ms 24804 KB Output is correct
10 Correct 13 ms 25176 KB Output is correct
11 Correct 16 ms 25844 KB Output is correct
12 Correct 19 ms 28244 KB Output is correct
13 Correct 62 ms 29156 KB Output is correct
14 Execution timed out 4067 ms 25860 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 14 ms 24412 KB Output is correct
3 Correct 17 ms 24156 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 14 ms 24012 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 10 ms 24156 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 13 ms 24804 KB Output is correct
10 Correct 13 ms 25176 KB Output is correct
11 Correct 229 ms 48360 KB Output is correct
12 Correct 613 ms 84496 KB Output is correct
13 Correct 150 ms 49732 KB Output is correct
14 Correct 669 ms 70976 KB Output is correct
15 Correct 743 ms 70752 KB Output is correct
16 Correct 630 ms 69716 KB Output is correct
17 Correct 150 ms 51024 KB Output is correct
18 Correct 1141 ms 232464 KB Output is correct
19 Correct 1399 ms 262144 KB Output is correct
20 Correct 424 ms 68944 KB Output is correct
21 Correct 16 ms 25844 KB Output is correct
22 Correct 19 ms 28244 KB Output is correct
23 Correct 62 ms 29156 KB Output is correct
24 Execution timed out 4067 ms 25860 KB Time limit exceeded
25 Halted 0 ms 0 KB -