oj.uz

Submission #988611

# Submission time Handle Problem Language Result Execution time Memory
988611 2024-05-25T09:49:24 Z huutuan Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 8664 KB 
#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int n;
   vector<int> lab;
   void init(int _n){
      n=_n;
      lab.assign(n+1, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   bool union_sets(int u, int v){
      u=find_set(u); v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
         return 1;
      }
      return 0;
   }
} dsu;

const int N=1e6+10;
int n, deg[N];
vector<pair<int, int>> edge;
bool check;

void Init(int N_) {
   n=N_;
}

void build(int u){
   for (int i=1; i<=n; ++i) deg[i]=0;
   check=1;
   dsu.init(n);
   for (auto &i:edge){
      if (i.first==u || i.second==u) continue;
      ++deg[i.first]; ++deg[i.second];
      check&=deg[i.first]<=2 && deg[i.second]<=2;
      check&=dsu.union_sets(i.first, i.second);
   }
}

void Link(int u, int v) {
   ++u; ++v;
   edge.emplace_back(u, v);
}

int CountCritical() {
   int ans=0;
   for (int i=1; i<=n; ++i) build(i), ans+=check;
   return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 143 ms 348 KB Output is correct
3 Correct 252 ms 604 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 56 ms 564 KB Output is correct
6 Correct 248 ms 644 KB Output is correct
7 Correct 35 ms 348 KB Output is correct
8 Correct 137 ms 572 KB Output is correct
9 Correct 276 ms 848 KB Output is correct
10 Correct 248 ms 644 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4025 ms 8664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 143 ms 348 KB Output is correct
3 Correct 252 ms 604 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 56 ms 564 KB Output is correct
6 Correct 248 ms 644 KB Output is correct
7 Correct 35 ms 348 KB Output is correct
8 Correct 137 ms 572 KB Output is correct
9 Correct 276 ms 848 KB Output is correct
10 Correct 248 ms 644 KB Output is correct
11 Execution timed out 4003 ms 624 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 143 ms 348 KB Output is correct
3 Correct 252 ms 604 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 56 ms 564 KB Output is correct
6 Correct 248 ms 644 KB Output is correct
7 Correct 35 ms 348 KB Output is correct
8 Correct 137 ms 572 KB Output is correct
9 Correct 276 ms 848 KB Output is correct
10 Correct 248 ms 644 KB Output is correct
11 Execution timed out 4003 ms 624 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 143 ms 348 KB Output is correct
3 Correct 252 ms 604 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 56 ms 564 KB Output is correct
6 Correct 248 ms 644 KB Output is correct
7 Correct 35 ms 348 KB Output is correct
8 Correct 137 ms 572 KB Output is correct
9 Correct 276 ms 848 KB Output is correct
10 Correct 248 ms 644 KB Output is correct
11 Execution timed out 4025 ms 8664 KB Time limit exceeded
12 Halted 0 ms 0 KB -