oj.uz

Submission #1020109

# Submission time Handle Problem Language Result Execution time Memory
1020109 2024-07-11T15:01:08 Z anton Parachute rings (IOI12_rings) C++17
37 / 100
 1306 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;
  }
  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){
        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){
            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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24156 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 6 ms 24784 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24412 KB Output is correct
6 Correct 6 ms 24668 KB Output is correct
7 Correct 4 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 8 ms 25236 KB Output is correct
10 Correct 8 ms 25692 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 54216 KB Output is correct
2 Correct 650 ms 93968 KB Output is correct
3 Correct 161 ms 51772 KB Output is correct
4 Correct 691 ms 81736 KB Output is correct
5 Correct 695 ms 81700 KB Output is correct
6 Correct 646 ms 79976 KB Output is correct
7 Correct 165 ms 52492 KB Output is correct
8 Correct 1160 ms 240652 KB Output is correct
9 Correct 1306 ms 262144 KB Output is correct
10 Correct 453 ms 82044 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24156 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 6 ms 24784 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24412 KB Output is correct
6 Correct 6 ms 24668 KB Output is correct
7 Correct 4 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 8 ms 25236 KB Output is correct
10 Correct 8 ms 25692 KB Output is correct
11 Incorrect 8 ms 26356 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24156 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 6 ms 24784 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24412 KB Output is correct
6 Correct 6 ms 24668 KB Output is correct
7 Correct 4 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 8 ms 25236 KB Output is correct
10 Correct 8 ms 25692 KB Output is correct
11 Incorrect 8 ms 26356 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24156 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 6 ms 24784 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 5 ms 24412 KB Output is correct
6 Correct 6 ms 24668 KB Output is correct
7 Correct 4 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 8 ms 25236 KB Output is correct
10 Correct 8 ms 25692 KB Output is correct
11 Correct 232 ms 54216 KB Output is correct
12 Correct 650 ms 93968 KB Output is correct
13 Correct 161 ms 51772 KB Output is correct
14 Correct 691 ms 81736 KB Output is correct
15 Correct 695 ms 81700 KB Output is correct
16 Correct 646 ms 79976 KB Output is correct
17 Correct 165 ms 52492 KB Output is correct
18 Correct 1160 ms 240652 KB Output is correct
19 Correct 1306 ms 262144 KB Output is correct
20 Correct 453 ms 82044 KB Output is correct
21 Incorrect 8 ms 26356 KB Output isn't correct
22 Halted 0 ms 0 KB -