oj.uz

Submission #1020244

# Submission time Handle Problem Language Result Execution time Memory
1020244 2024-07-11T18:10:11 Z anton Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 146056 KB 
#include<bits/stdc++.h>

using namespace std;

struct DSU{
  int nbGroups =0;
  bool needs_op_buffer = false;
  vector<int> anc;
  vector<int> sz;
  vector<pair<int, pair<int, int>>> op_buffer;
  int nbCycles = 0;
  int szCycle= 0;

  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){
    
    if(needs_op_buffer)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--;

    if(needs_op_buffer)op_buffer.push_back({a, {anc[a], sz[a]}});
    if(needs_op_buffer)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 boringDSU, fullDSU;
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;
}

int state = 0;
//0 = only deg<=2
//1 only deg <=3, some interesting left
//2 One deg =4, some interesting
//3 no interesting left
void changeDeg(int u, int d){
  
  if(deg[u]>=3){
    above3--;
  }
  if(deg[u] >= 4){
    above4--;
  }
  oc[deg[u]]--;
  deg[u] +=d;
  assert(deg[u]>=0);
  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);
  fill(&isInteresting[0], &isInteresting[N], true);

  for(int i = 0; i<N; i++){
    interesting.push_back(i);
  }
  oc[0]  =N;
  boringDSU = DSU(N);
  fullDSU = DSU(N);
  boringDSU.needs_op_buffer = true;
}

void updInteresting(int u, bool tolerant){
  unordered_set<int> close;
  if(tolerant){
    for(auto e: adj[u]){
        close.insert(e);
    }
  }
  close.insert(u);
  vector<int> new_interesting;
  for(int i = 0; i<interesting.size(); i++){
    auto it = interesting[i];
    if(close.find(it)  == close.end()){
      isInteresting[it] = false;
      //cerr<<"removing "<<*it<<endl;
      for(auto ee: adj[it]){
        if(!isInteresting[ee]){
          boringDSU.merge(it, ee);
        }
      }
    }
    else{
      new_interesting.push_back(it);
    }
  }

  swap(interesting, new_interesting);
}

void recalcDeg(){
    for(int i = 0; i<N; i++){
        if(deg[i] < 4){
          changeDeg(i, -deg[i]);
          for(auto v: adj[i]){
              if(deg[v] != 4){
                   changeDeg(i, 1);
              }
          }
        }
    }
}

void Link(int A, int B) {
    if(interesting.size()== 0){
        return;
    }

    fullDSU.merge(A, B);

    adj[A].push_back(B);
    adj[B].push_back(A);

    if(deg[A] <4 && deg[B] < 4){
        changeDeg(A, +1);
        changeDeg(B, +1);
    }
    if((deg[A]== 3 || deg[B]==3)){

        if(deg[A] != 3){
        swap(A, B);
        }
        updInteresting(A, true);
        if(deg[B] == 3){
            updInteresting(B, true);
        }
    }

    if(isInteresting[A] || isInteresting[B]){

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

    if((deg[A] == 4 || deg[B]== 4) && above4 == 1){
        if(deg[A] != 4){
            swap(A, B);
        }
        updInteresting(A, false);
        if(deg[B] == 4){
            updInteresting(B, false);
        } 
        recalcDeg();
    }
}

int prev_res=  0;

int calc(){
  if(interesting.size() == 0){
    return 0;
  }
  else{
    if(above4 == 1){
        if((oc[0])*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==1){
            return 1;
        }
        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);
        }
      }
      boringDSU.op_buffer.clear();

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


          
          if((oc[0]-1)*2 + oc[1] == (boringDSU.nbGroups-1)*2 && above3 ==0){
            res++;
            //cerr<<iRem<<endl;
          }
          else{
            //cerr<<oc[0]<<" "<<oc[1]<<" "<<oc[2]<<endl;
          }


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


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

int CountCritical() {
  //cerr<<oc[0]<<" "<<oc[1]<<" "<<oc[2]<<" "<<oc[3]<<endl;
  prev_res = calc();
  return prev_res;

}

Compilation message

rings.cpp: In function 'void updInteresting(int, bool)':
rings.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   for(int i = 0; i<interesting.size(); i++){
      |                  ~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 12 ms 24260 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 10 ms 23892 KB Output is correct
5 Correct 12 ms 24152 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 12 ms 24184 KB Output is correct
10 Correct 15 ms 24488 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 58568 KB Output is correct
2 Correct 870 ms 90296 KB Output is correct
3 Correct 185 ms 56084 KB Output is correct
4 Correct 609 ms 90304 KB Output is correct
5 Correct 606 ms 90464 KB Output is correct
6 Correct 608 ms 88940 KB Output is correct
7 Correct 159 ms 56436 KB Output is correct
8 Correct 731 ms 137872 KB Output is correct
9 Correct 769 ms 146056 KB Output is correct
10 Correct 462 ms 94396 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 12 ms 24260 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 10 ms 23892 KB Output is correct
5 Correct 12 ms 24152 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 12 ms 24184 KB Output is correct
10 Correct 15 ms 24488 KB Output is correct
11 Correct 13 ms 24412 KB Output is correct
12 Correct 13 ms 25432 KB Output is correct
13 Correct 13 ms 24920 KB Output is correct
14 Correct 141 ms 24308 KB Output is correct
15 Correct 383 ms 24408 KB Output is correct
16 Correct 13 ms 24484 KB Output is correct
17 Correct 12 ms 24156 KB Output is correct
18 Correct 13 ms 24696 KB Output is correct
19 Correct 13 ms 24664 KB Output is correct
20 Correct 13 ms 24960 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 12 ms 24260 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 10 ms 23892 KB Output is correct
5 Correct 12 ms 24152 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 12 ms 24184 KB Output is correct
10 Correct 15 ms 24488 KB Output is correct
11 Correct 13 ms 24412 KB Output is correct
12 Correct 13 ms 25432 KB Output is correct
13 Correct 13 ms 24920 KB Output is correct
14 Correct 141 ms 24308 KB Output is correct
15 Correct 383 ms 24408 KB Output is correct
16 Correct 13 ms 24484 KB Output is correct
17 Correct 12 ms 24156 KB Output is correct
18 Correct 13 ms 24696 KB Output is correct
19 Correct 13 ms 24664 KB Output is correct
20 Correct 13 ms 24960 KB Output is correct
21 Correct 27 ms 26344 KB Output is correct
22 Correct 30 ms 27712 KB Output is correct
23 Correct 34 ms 28876 KB Output is correct
24 Execution timed out 4009 ms 27436 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 12 ms 24260 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 10 ms 23892 KB Output is correct
5 Correct 12 ms 24152 KB Output is correct
6 Correct 12 ms 24156 KB Output is correct
7 Correct 11 ms 23896 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 12 ms 24184 KB Output is correct
10 Correct 15 ms 24488 KB Output is correct
11 Correct 214 ms 58568 KB Output is correct
12 Correct 870 ms 90296 KB Output is correct
13 Correct 185 ms 56084 KB Output is correct
14 Correct 609 ms 90304 KB Output is correct
15 Correct 606 ms 90464 KB Output is correct
16 Correct 608 ms 88940 KB Output is correct
17 Correct 159 ms 56436 KB Output is correct
18 Correct 731 ms 137872 KB Output is correct
19 Correct 769 ms 146056 KB Output is correct
20 Correct 462 ms 94396 KB Output is correct
21 Correct 13 ms 24412 KB Output is correct
22 Correct 13 ms 25432 KB Output is correct
23 Correct 13 ms 24920 KB Output is correct
24 Correct 141 ms 24308 KB Output is correct
25 Correct 383 ms 24408 KB Output is correct
26 Correct 13 ms 24484 KB Output is correct
27 Correct 12 ms 24156 KB Output is correct
28 Correct 13 ms 24696 KB Output is correct
29 Correct 13 ms 24664 KB Output is correct
30 Correct 13 ms 24960 KB Output is correct
31 Correct 27 ms 26344 KB Output is correct
32 Correct 30 ms 27712 KB Output is correct
33 Correct 34 ms 28876 KB Output is correct
34 Execution timed out 4009 ms 27436 KB Time limit exceeded
35 Halted 0 ms 0 KB -