oj.uz

Submission #1020797

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

using namespace std;


struct DSU{
  vector<int> sz, anc, oc, deg;
  int nbG= 0, nbC= 0, csz = 0, above3 = 0;
  DSU(){};
  DSU(int l){
    sz.resize(l);
    anc.resize(l);
    oc.resize(l);
    deg.resize(l);
    nbG = l;
    for(int i = 0; i<l; i++){
      anc[i] = i;
      sz[i] = 1;
      deg[i] = 0;
    }
    oc[0]= l;
  }


  int c(int u){
    if(anc[u] == u){
      return u;
    }
    int v= c(anc[u]);
    anc[u] = v;
    return v;
  }

  void changeDeg(int u, int d){
    oc[deg[u]]--;
    if(deg[u]>=3){
      above3--;
    }
    deg[u]+=d;
    if(deg[u]>=3){
      above3++;
    }
    oc[deg[u]]++;
  }

  void merge(int a, int b){

    changeDeg(a, +1);
    changeDeg(b, +1);
    a=  c(a);
    b = c(b);
    if(a==b){
      nbC++;
      csz = sz[a];
      return;
    }
    nbG--;

    if(sz[a]<sz[b]){
      swap(a, b);
    }
    
    anc[b]= a;
    sz[a]+=sz[b];
  }
};

struct multiDSU{
  unordered_map<int, DSU> dsus;

  multiDSU(){};
  multiDSU(int l, unordered_set<int>& intresting){
    for(auto e: intresting){
      dsus[e] = DSU(l);
    }
    dsus[-1] = DSU(l);
  }

  void merge(int a, int b){
    for(auto it = dsus.begin(); it!=dsus.end(); ++it){
      if(it->first != a && it->first != b){
        //cerr<<"merging "<<a<<" "<<b<<" "<<it->first<<endl;
        it->second.merge(a, b);
      }
    }
  }
};
const int MAX_N = 1e6;
vector<int> adj[MAX_N];
DSU beginDSU;
multiDSU endDSU;

int N;
int state = 0;
//0 = only 2s
//1 = have a 3 or more
void Init(int _N){
  N = _N;
  beginDSU = DSU(N);
}
void Link(int a, int b){
  if(state == 0){
    beginDSU.merge(a, b);
    adj[a].push_back(b);
    adj[b].push_back(a);
    if(adj[a].size()<3){
      swap(a, b);
    }
    if(adj[a].size() >= 3){
      state = 1;
      unordered_set<int> intresting;
      for(auto o: adj[a]){
        intresting.insert(o);
      }
      intresting.insert(a);
      endDSU = multiDSU(N, intresting);
      for(int i = 0; i<N; i++){
        for(auto e: adj[i]){
          if(i<e){
            endDSU.merge(e, i);
          }
        }
      }
    }
  }
  else{
    endDSU.merge(a, b);
  }
}

int CountCritical(){
  if(state== 0){
    if(beginDSU.nbC == 0){
      return N;
    }
    else if(beginDSU.nbC == 1){
      return beginDSU.csz;
    }
    else{
      return 0;
    }
  }
  else{
    int res= 0;
    for(auto e: endDSU.dsus){
      if(e.first != -1){

        if((e.second.oc[0]-1)*2 + e.second.oc[1] == 2*(e.second.nbG-1) && e.second.above3 == 0){
          res++;
        }
        else{
        }
      }
    }
    return res;
  }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23896 KB Output is correct
2 Correct 6 ms 24412 KB Output is correct
3 Correct 6 ms 24412 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 6 ms 24412 KB Output is correct
7 Correct 4 ms 24428 KB Output is correct
8 Correct 6 ms 24152 KB Output is correct
9 Correct 7 ms 24408 KB Output is correct
10 Correct 5 ms 24668 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 55204 KB Output is correct
2 Correct 884 ms 136352 KB Output is correct
3 Correct 1073 ms 146620 KB Output is correct
4 Correct 620 ms 84044 KB Output is correct
5 Correct 594 ms 84260 KB Output is correct
6 Correct 539 ms 82512 KB Output is correct
7 Correct 1045 ms 146212 KB Output is correct
8 Correct 1054 ms 165300 KB Output is correct
9 Correct 1190 ms 177328 KB Output is correct
10 Correct 376 ms 81752 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23896 KB Output is correct
2 Correct 6 ms 24412 KB Output is correct
3 Correct 6 ms 24412 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 6 ms 24412 KB Output is correct
7 Correct 4 ms 24428 KB Output is correct
8 Correct 6 ms 24152 KB Output is correct
9 Correct 7 ms 24408 KB Output is correct
10 Correct 5 ms 24668 KB Output is correct
11 Correct 6 ms 24412 KB Output is correct
12 Correct 10 ms 25468 KB Output is correct
13 Correct 14 ms 25352 KB Output is correct
14 Correct 16 ms 25144 KB Output is correct
15 Correct 47 ms 26244 KB Output is correct
16 Correct 10 ms 24412 KB Output is correct
17 Correct 21 ms 25184 KB Output is correct
18 Correct 52 ms 26320 KB Output is correct
19 Correct 7 ms 24408 KB Output is correct
20 Correct 13 ms 25420 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23896 KB Output is correct
2 Correct 6 ms 24412 KB Output is correct
3 Correct 6 ms 24412 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 6 ms 24412 KB Output is correct
7 Correct 4 ms 24428 KB Output is correct
8 Correct 6 ms 24152 KB Output is correct
9 Correct 7 ms 24408 KB Output is correct
10 Correct 5 ms 24668 KB Output is correct
11 Correct 6 ms 24412 KB Output is correct
12 Correct 10 ms 25468 KB Output is correct
13 Correct 14 ms 25352 KB Output is correct
14 Correct 16 ms 25144 KB Output is correct
15 Correct 47 ms 26244 KB Output is correct
16 Correct 10 ms 24412 KB Output is correct
17 Correct 21 ms 25184 KB Output is correct
18 Correct 52 ms 26320 KB Output is correct
19 Correct 7 ms 24408 KB Output is correct
20 Correct 13 ms 25420 KB Output is correct
21 Correct 15 ms 25948 KB Output is correct
22 Correct 22 ms 27228 KB Output is correct
23 Correct 28 ms 28272 KB Output is correct
24 Execution timed out 4066 ms 34744 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23896 KB Output is correct
2 Correct 6 ms 24412 KB Output is correct
3 Correct 6 ms 24412 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 6 ms 24412 KB Output is correct
7 Correct 4 ms 24428 KB Output is correct
8 Correct 6 ms 24152 KB Output is correct
9 Correct 7 ms 24408 KB Output is correct
10 Correct 5 ms 24668 KB Output is correct
11 Correct 205 ms 55204 KB Output is correct
12 Correct 884 ms 136352 KB Output is correct
13 Correct 1073 ms 146620 KB Output is correct
14 Correct 620 ms 84044 KB Output is correct
15 Correct 594 ms 84260 KB Output is correct
16 Correct 539 ms 82512 KB Output is correct
17 Correct 1045 ms 146212 KB Output is correct
18 Correct 1054 ms 165300 KB Output is correct
19 Correct 1190 ms 177328 KB Output is correct
20 Correct 376 ms 81752 KB Output is correct
21 Correct 6 ms 24412 KB Output is correct
22 Correct 10 ms 25468 KB Output is correct
23 Correct 14 ms 25352 KB Output is correct
24 Correct 16 ms 25144 KB Output is correct
25 Correct 47 ms 26244 KB Output is correct
26 Correct 10 ms 24412 KB Output is correct
27 Correct 21 ms 25184 KB Output is correct
28 Correct 52 ms 26320 KB Output is correct
29 Correct 7 ms 24408 KB Output is correct
30 Correct 13 ms 25420 KB Output is correct
31 Correct 15 ms 25948 KB Output is correct
32 Correct 22 ms 27228 KB Output is correct
33 Correct 28 ms 28272 KB Output is correct
34 Execution timed out 4066 ms 34744 KB Time limit exceeded
35 Halted 0 ms 0 KB -