oj.uz

Submission #589798

# Submission time Handle Problem Language Result Execution time Memory
589798 2022-07-05T09:41:14 Z daria Parachute rings (IOI12_rings) C++14
100 / 100
 1758 ms 133532 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll int
#define MAXN 1000005
#define _ << " " <<
//definizioni globali

vector<array<ll, 2> > edges;
ll ris=-1, stato = 0;
ll n;
vector<ll> adj[MAXN];

struct grafo{
 ll par[MAXN], size[MAXN], deg[MAXN];
 ll can = -1, nc = 0, idx = -1;

 //union find
 ll find(ll a){
  if(par[a] == a) return a;
  return par[a]=find(par[a]);
 }

 bool same(ll a, ll b){
  return find(a) == find(b);
 }

 void unite(ll a, ll b){
  a = find(a);
  b = find(b);
  if(size[a] > size[b]) swap(a, b);
  par[a] = b;
  size[b] += size[a];
 }

 //archi
 void link(ll a, ll b){
  if(a == can || b == can) return;
  //cout << a _ b _ idx <<  " ";
  deg[a]++;
  deg[b]++;
  bool check = 0;
  if(deg[a] == 2 && deg[b] == 2 && same(a, b)) check = 1; //creo un ciclo
  if(deg[a] == 3 || deg[b] ==  3) check = 1; //nodo con grado >= 3

  if(!same(a, b)) unite(a, b);

  if(check){
   if(idx == -1 || !same(idx, a)){
    nc++; idx = a;
   }
  }
  if(idx != -1) idx = find(idx);
  //cout << idx << endl;
 }

 //build
 void init(ll n){
  for(ll i=0; i<n; ++i){
   par[i] = i;
   size[i] = 1;
  }
  for(auto u : edges)
   link(u[0], u[1]);
 }

};


grafo G[5];

void Init(int N) {
 n = N;
 G[0].init(N);
}

void Link(int a, int b) {
 if(stato == 0) edges.push_back({a, b});
 adj[a].push_back(b);
 adj[b].push_back(a);
 grafo &g = G[0];
 g.link(a, b);
 for(ll i=0; i<n; ++i){
  //cout << i _ g.find(i) << endl;
 }
 // aggiorno i 4 grafi alternativi
 if(stato == 1) for(ll i=1; i<5; ++i) G[i].link(a, b);

 //primo nodo con grado >= 3
 if(stato == 0){
  if(g.deg[a] == 3){
   stato = 1;
   G[1].can = a; G[2].can = adj[a][0]; G[3].can = adj[a][1]; G[4].can = adj[a][2]; }
  else if(g.deg[b] == 3){
   stato = 1;
   G[1].can = b; G[2].can = adj[b][0]; G[3].can = adj[b][1]; G[4].can = adj[b][2]; }

  // costruisco i 4 grafi alternativi
  if(stato == 1) for(ll i=1; i<5; ++i) G[i].init(n);
 }
}


int CountCritical() {
 if(ris == 0)
  return 0;

 grafo &g = G[0];

 //cout << endl <<  g.nc << " " << g.idx << endl;
 if(g.nc == 0)
  return n;

 if(g.nc >= 2)
  return ris = 0;

 //g.nc == 1
 if(stato == 0)
  return g.size[g.idx];

 //stato >= 1
 ll cnt =0;
 for(ll i= 1; i<5; ++i)
  cnt += (G[i].nc == 0);
 return ris = cnt;

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 24276 KB Output is correct
3 Correct 17 ms 24328 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 15 ms 24148 KB Output is correct
7 Correct 12 ms 24188 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 15 ms 24404 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 50360 KB Output is correct
2 Correct 1352 ms 108532 KB Output is correct
3 Correct 1758 ms 122484 KB Output is correct
4 Correct 1040 ms 88004 KB Output is correct
5 Correct 1042 ms 87976 KB Output is correct
6 Correct 987 ms 86336 KB Output is correct
7 Correct 1575 ms 121460 KB Output is correct
8 Correct 1571 ms 125752 KB Output is correct
9 Correct 1634 ms 133532 KB Output is correct
10 Correct 689 ms 85108 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 24276 KB Output is correct
3 Correct 17 ms 24328 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 15 ms 24148 KB Output is correct
7 Correct 12 ms 24188 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 15 ms 24404 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 14 ms 24404 KB Output is correct
12 Correct 17 ms 24916 KB Output is correct
13 Correct 19 ms 24788 KB Output is correct
14 Correct 18 ms 24696 KB Output is correct
15 Correct 16 ms 25172 KB Output is correct
16 Correct 15 ms 24404 KB Output is correct
17 Correct 17 ms 24820 KB Output is correct
18 Correct 22 ms 25544 KB Output is correct
19 Correct 15 ms 24404 KB Output is correct
20 Correct 19 ms 24788 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 24276 KB Output is correct
3 Correct 17 ms 24328 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 15 ms 24148 KB Output is correct
7 Correct 12 ms 24188 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 15 ms 24404 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 14 ms 24404 KB Output is correct
12 Correct 17 ms 24916 KB Output is correct
13 Correct 19 ms 24788 KB Output is correct
14 Correct 18 ms 24696 KB Output is correct
15 Correct 16 ms 25172 KB Output is correct
16 Correct 15 ms 24404 KB Output is correct
17 Correct 17 ms 24820 KB Output is correct
18 Correct 22 ms 25544 KB Output is correct
19 Correct 15 ms 24404 KB Output is correct
20 Correct 19 ms 24788 KB Output is correct
21 Correct 34 ms 25592 KB Output is correct
22 Correct 40 ms 26596 KB Output is correct
23 Correct 46 ms 27432 KB Output is correct
24 Correct 88 ms 30908 KB Output is correct
25 Correct 30 ms 30036 KB Output is correct
26 Correct 105 ms 31536 KB Output is correct
27 Correct 65 ms 28212 KB Output is correct
28 Correct 72 ms 31816 KB Output is correct
29 Correct 55 ms 31384 KB Output is correct
30 Correct 57 ms 28864 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 24276 KB Output is correct
3 Correct 17 ms 24328 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 16 ms 24020 KB Output is correct
6 Correct 15 ms 24148 KB Output is correct
7 Correct 12 ms 24188 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 15 ms 24404 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 440 ms 50360 KB Output is correct
12 Correct 1352 ms 108532 KB Output is correct
13 Correct 1758 ms 122484 KB Output is correct
14 Correct 1040 ms 88004 KB Output is correct
15 Correct 1042 ms 87976 KB Output is correct
16 Correct 987 ms 86336 KB Output is correct
17 Correct 1575 ms 121460 KB Output is correct
18 Correct 1571 ms 125752 KB Output is correct
19 Correct 1634 ms 133532 KB Output is correct
20 Correct 689 ms 85108 KB Output is correct
21 Correct 14 ms 24404 KB Output is correct
22 Correct 17 ms 24916 KB Output is correct
23 Correct 19 ms 24788 KB Output is correct
24 Correct 18 ms 24696 KB Output is correct
25 Correct 16 ms 25172 KB Output is correct
26 Correct 15 ms 24404 KB Output is correct
27 Correct 17 ms 24820 KB Output is correct
28 Correct 22 ms 25544 KB Output is correct
29 Correct 15 ms 24404 KB Output is correct
30 Correct 19 ms 24788 KB Output is correct
31 Correct 34 ms 25592 KB Output is correct
32 Correct 40 ms 26596 KB Output is correct
33 Correct 46 ms 27432 KB Output is correct
34 Correct 88 ms 30908 KB Output is correct
35 Correct 30 ms 30036 KB Output is correct
36 Correct 105 ms 31536 KB Output is correct
37 Correct 65 ms 28212 KB Output is correct
38 Correct 72 ms 31816 KB Output is correct
39 Correct 55 ms 31384 KB Output is correct
40 Correct 57 ms 28864 KB Output is correct
41 Correct 210 ms 43392 KB Output is correct
42 Correct 690 ms 98428 KB Output is correct
43 Correct 295 ms 85088 KB Output is correct
44 Correct 1182 ms 118224 KB Output is correct
45 Correct 1100 ms 112364 KB Output is correct
46 Correct 723 ms 77936 KB Output is correct
47 Correct 868 ms 78764 KB Output is correct
48 Correct 684 ms 105532 KB Output is correct
49 Correct 699 ms 76948 KB Output is correct
50 Correct 733 ms 76504 KB Output is correct
51 Correct 420 ms 79204 KB Output is correct
52 Correct 1085 ms 100208 KB Output is correct
53 Correct 709 ms 105692 KB Output is correct
54 Correct 1355 ms 111084 KB Output is correct
55 Correct 1719 ms 115288 KB Output is correct