oj.uz

Submission #988778

# Submission time Handle Problem Language Result Execution time Memory
988778 2024-05-26T03:40:26 Z huutuan Parachute rings (IOI12_rings) C++14
37 / 100
 1281 ms 250656 KB 
#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int n, check, idx, cnt, mxdeg;
   vector<int> lab, deg;
   void init(int _n){
      n=_n; check=1; idx=-1; cnt=0; mxdeg=0;
      lab.assign(n+1, -1);
      deg.assign(n+1, 0);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      ++deg[u], ++deg[v]; mxdeg=max({mxdeg, deg[u], deg[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;
         if (idx==v) idx=u;
      }else check=0, idx=u, ++cnt;
   }
} dsu[20], dsu2;

const int N=1e6+10;
int n, deg[N];
set<int> st3, st4;
vector<pair<int, int>> edge;
bool cc;
vector<int> cand, g[N];

void Init(int N_) {
   n=N_;
   dsu2.init(n+1);
}

void add_cand(int u){
   if (find(cand.begin(), cand.end(), u)!=cand.end() || (int)cand.size()>20) return;
   int id=cand.size();
   cand.push_back(u);
   if (id<20){
      dsu[id].init(n+1);
      for (auto &i:edge) if (i.first!=u && i.second!=u) dsu[id].union_sets(i.first, i.second);
   }
}

void Link(int u, int v) {
   ++u; ++v;
   edge.emplace_back(u, v);
   if ((int)cand.size()<=20){
      for (int i=0; i<(int)cand.size(); ++i){
         if (u==cand[i] || v==cand[i]) continue;
         dsu[i].union_sets(u, v);
      }
   }
   dsu2.union_sets(u, v);
   st3.erase(u); st3.erase(v);
   ++deg[u]; ++deg[v];
   g[u].push_back(v);
   g[v].push_back(u);
   if (deg[u]==3) st3.insert(u);
   if (deg[v]==3) st3.insert(v);
   if (deg[u]==4) st4.insert(u);
   if (deg[v]==4) st4.insert(v);
   if ((int)st3.size()+(int)st4.size()<=10){
      for (int u:st4) add_cand(u);
      for (int u:st3){
         add_cand(u);
         for (int v:g[u]) add_cand(v);
      }
   }
}

int CountCritical() {
   if (st3.empty() && st4.empty()){
      if (dsu2.check) return n;
      if (dsu2.cnt==1) return -dsu2.lab[dsu2.idx];
      return 0;
   }
   if ((int)cand.size()>20) return 0;
   int ans=0;
   for (int i=0; i<(int)cand.size(); ++i){
      ans+=dsu[i].check && dsu[i].mxdeg<=2;
   }
   return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 4 ms 25180 KB Output is correct
5 Correct 6 ms 25264 KB Output is correct
6 Correct 6 ms 25600 KB Output is correct
7 Correct 5 ms 26012 KB Output is correct
8 Correct 5 ms 25432 KB Output is correct
9 Correct 6 ms 25724 KB Output is correct
10 Correct 6 ms 25688 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 51644 KB Output is correct
2 Correct 693 ms 91312 KB Output is correct
3 Correct 1281 ms 240792 KB Output is correct
4 Correct 497 ms 74676 KB Output is correct
5 Correct 547 ms 88124 KB Output is correct
6 Correct 543 ms 86196 KB Output is correct
7 Correct 1190 ms 250656 KB Output is correct
8 Correct 900 ms 127884 KB Output is correct
9 Correct 862 ms 142928 KB Output is correct
10 Correct 365 ms 85424 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 4 ms 25180 KB Output is correct
5 Correct 6 ms 25264 KB Output is correct
6 Correct 6 ms 25600 KB Output is correct
7 Correct 5 ms 26012 KB Output is correct
8 Correct 5 ms 25432 KB Output is correct
9 Correct 6 ms 25724 KB Output is correct
10 Correct 6 ms 25688 KB Output is correct
11 Correct 7 ms 26204 KB Output is correct
12 Correct 9 ms 27228 KB Output is correct
13 Correct 9 ms 27276 KB Output is correct
14 Incorrect 8 ms 27092 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 4 ms 25180 KB Output is correct
5 Correct 6 ms 25264 KB Output is correct
6 Correct 6 ms 25600 KB Output is correct
7 Correct 5 ms 26012 KB Output is correct
8 Correct 5 ms 25432 KB Output is correct
9 Correct 6 ms 25724 KB Output is correct
10 Correct 6 ms 25688 KB Output is correct
11 Correct 7 ms 26204 KB Output is correct
12 Correct 9 ms 27228 KB Output is correct
13 Correct 9 ms 27276 KB Output is correct
14 Incorrect 8 ms 27092 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 6 ms 25692 KB Output is correct
4 Correct 4 ms 25180 KB Output is correct
5 Correct 6 ms 25264 KB Output is correct
6 Correct 6 ms 25600 KB Output is correct
7 Correct 5 ms 26012 KB Output is correct
8 Correct 5 ms 25432 KB Output is correct
9 Correct 6 ms 25724 KB Output is correct
10 Correct 6 ms 25688 KB Output is correct
11 Correct 179 ms 51644 KB Output is correct
12 Correct 693 ms 91312 KB Output is correct
13 Correct 1281 ms 240792 KB Output is correct
14 Correct 497 ms 74676 KB Output is correct
15 Correct 547 ms 88124 KB Output is correct
16 Correct 543 ms 86196 KB Output is correct
17 Correct 1190 ms 250656 KB Output is correct
18 Correct 900 ms 127884 KB Output is correct
19 Correct 862 ms 142928 KB Output is correct
20 Correct 365 ms 85424 KB Output is correct
21 Correct 7 ms 26204 KB Output is correct
22 Correct 9 ms 27228 KB Output is correct
23 Correct 9 ms 27276 KB Output is correct
24 Incorrect 8 ms 27092 KB Output isn't correct
25 Halted 0 ms 0 KB -