oj.uz

Submission #1020086

# Submission time Handle Problem Language Result Execution time Memory
1020086 2024-07-11T14:15:18 Z anton Parachute rings (IOI12_rings) C++17
0 / 100
 1087 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){
    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 countInterestingAdj(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);

}

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);
      }
    }
    curDSU = recalcDSU();
     
  }
  else if(isInteresting[A] || isInteresting[B]){

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

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

int CountCritical() {
  if(above4>1 || lost3){
    return 0;
  }
  if(above4 == 1){
    return 1;
  }
  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){

        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){
          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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 11 ms 24412 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 11 ms 23896 KB Output is correct
5 Correct 11 ms 23988 KB Output is correct
6 Correct 12 ms 24152 KB Output is correct
7 Correct 11 ms 24156 KB Output is correct
8 Correct 14 ms 24156 KB Output is correct
9 Correct 13 ms 24856 KB Output is correct
10 Incorrect 14 ms 25440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 55040 KB Output is correct
2 Correct 597 ms 95188 KB Output is correct
3 Correct 158 ms 54124 KB Output is correct
4 Correct 656 ms 84248 KB Output is correct
5 Correct 663 ms 84304 KB Output is correct
6 Correct 665 ms 82768 KB Output is correct
7 Correct 149 ms 54508 KB Output is correct
8 Correct 1034 ms 242060 KB Output is correct
9 Incorrect 1087 ms 262144 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 11 ms 24412 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 11 ms 23896 KB Output is correct
5 Correct 11 ms 23988 KB Output is correct
6 Correct 12 ms 24152 KB Output is correct
7 Correct 11 ms 24156 KB Output is correct
8 Correct 14 ms 24156 KB Output is correct
9 Correct 13 ms 24856 KB Output is correct
10 Incorrect 14 ms 25440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 11 ms 24412 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 11 ms 23896 KB Output is correct
5 Correct 11 ms 23988 KB Output is correct
6 Correct 12 ms 24152 KB Output is correct
7 Correct 11 ms 24156 KB Output is correct
8 Correct 14 ms 24156 KB Output is correct
9 Correct 13 ms 24856 KB Output is correct
10 Incorrect 14 ms 25440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 11 ms 24412 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 11 ms 23896 KB Output is correct
5 Correct 11 ms 23988 KB Output is correct
6 Correct 12 ms 24152 KB Output is correct
7 Correct 11 ms 24156 KB Output is correct
8 Correct 14 ms 24156 KB Output is correct
9 Correct 13 ms 24856 KB Output is correct
10 Incorrect 14 ms 25440 KB Output isn't correct
11 Halted 0 ms 0 KB -