oj.uz

Submission #1020241

# Submission time Handle Problem Language Result Execution time Memory
1020241 2024-07-11T18:05:54 Z anton Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 8152 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= 1e5;
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 1 ms 2652 KB Output is correct
2 Correct 2 ms 3252 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2820 KB Output is correct
6 Correct 2 ms 3068 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 3 ms 3164 KB Output is correct
10 Correct 3 ms 3352 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 7256 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 3252 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2820 KB Output is correct
6 Correct 2 ms 3068 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 3 ms 3164 KB Output is correct
10 Correct 3 ms 3352 KB Output is correct
11 Correct 3 ms 3360 KB Output is correct
12 Correct 5 ms 4440 KB Output is correct
13 Correct 5 ms 3928 KB Output is correct
14 Correct 130 ms 3280 KB Output is correct
15 Correct 333 ms 3540 KB Output is correct
16 Correct 4 ms 3420 KB Output is correct
17 Correct 3 ms 3140 KB Output is correct
18 Correct 3 ms 3420 KB Output is correct
19 Correct 3 ms 3420 KB Output is correct
20 Correct 4 ms 3852 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 3252 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2820 KB Output is correct
6 Correct 2 ms 3068 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 3 ms 3164 KB Output is correct
10 Correct 3 ms 3352 KB Output is correct
11 Correct 3 ms 3360 KB Output is correct
12 Correct 5 ms 4440 KB Output is correct
13 Correct 5 ms 3928 KB Output is correct
14 Correct 130 ms 3280 KB Output is correct
15 Correct 333 ms 3540 KB Output is correct
16 Correct 4 ms 3420 KB Output is correct
17 Correct 3 ms 3140 KB Output is correct
18 Correct 3 ms 3420 KB Output is correct
19 Correct 3 ms 3420 KB Output is correct
20 Correct 4 ms 3852 KB Output is correct
21 Correct 14 ms 5468 KB Output is correct
22 Correct 27 ms 7160 KB Output is correct
23 Correct 26 ms 8152 KB Output is correct
24 Execution timed out 4098 ms 6828 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 3252 KB Output is correct
3 Correct 3 ms 3164 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2820 KB Output is correct
6 Correct 2 ms 3068 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 3 ms 3164 KB Output is correct
10 Correct 3 ms 3352 KB Output is correct
11 Runtime error 4 ms 7256 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -