oj.uz

Submission #802487

# Submission time Handle Problem Language Result Execution time Memory
802487 2023-08-02T12:31:15 Z Dan4Life Parachute rings (IOI12_rings) C++17
100 / 100
 1710 ms 124440 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
const int N = (int)1e6+9;
vector<int> v, adj[N];
array<int,2> edges[N];
int n, s=-1, T=1, ok=1, totE;
 
struct Dsu{
    bitset<N> bad;
    int deg[N], p[N], sz[N];
    int node, numBad, cycSz;
    void init(int N){
        node = -1; numBad=cycSz=0;
        for(int i = 0; i < N; i++)
            p[i]=i,sz[i]=1, bad[i]=deg[i]=0; 
    }
    int findSet(int i){ return i==p[i]?i:p[i]=findSet(p[i]); }
    void unionSet(int i, int j){
        if(i==node or j==node) return;
        deg[i]++, deg[j]++;
        int x = findSet(i), y = findSet(j);
        if(x==y){ 
            if(!bad[x]) numBad++, bad[x]=1;
            cycSz = sz[x]; return;
        }
        numBad-=bad[x]+bad[y];
        if(sz[x]<sz[y]) swap(x,y);
        p[y] = x; sz[x]+=sz[y];
        if(bad[x]||bad[y]||deg[i]>2||deg[j]>2)
            bad[x]=bad[y]=1, numBad++;
    }
} dsu[5];
 
void Init(int n_) { n = n_; for(int i=0;i<5;i++) dsu[i].init(n); }
 
void Link(int a, int b) {
    edges[totE++]={a,b}; adj[a].pb(b); adj[b].pb(a);
    for(int i=0;i<T;i++) dsu[i].unionSet(a,b);
    if(dsu[0].deg[a]==4 and sz(v)<=1) v.pb(a);
    if(dsu[0].deg[b]==4 and sz(v)<=1) v.pb(b);
    if(dsu[0].deg[a]==3 and s==-1) s=a;
    if(dsu[0].deg[b]==3 and s==-1) s=b;
}
 
int CountCritical(){
    if(sz(v)>=2 or dsu[0].numBad>=2) return 0;
    if(!dsu[0].numBad) return n;
    if(sz(v)==1){
        if(ok){
            dsu[T++].node = v[0]; ok=0;
            for(int i = 0; i < totE; i++)
                dsu[1].unionSet(edges[i][0],edges[i][1]);
        }
        return !dsu[1].numBad;
    }
    if(s==-1) return dsu[0].cycSz;
    if(ok){
        dsu[T++].node=s; ok = 0;
        for(auto u : adj[s]) dsu[T++].node=u;
          for(int i = totE-1; i >= 0; i--)
        		for(int j = 1; j < T; j++)
              		dsu[j].unionSet(edges[i][0],edges[i][1]);
    }
    int ans=0;for(int i=1;i<T;i++)ans+=!dsu[i].numBad; return ans;
}

Compilation message

rings.cpp: In member function 'void Dsu::init(int)':
rings.cpp:17:42: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   17 |             p[i]=i,sz[i]=1, bad[i]=deg[i]=0;
      |                                    ~~~~~~^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24536 KB Output is correct
2 Correct 15 ms 24844 KB Output is correct
3 Correct 15 ms 25076 KB Output is correct
4 Correct 12 ms 24572 KB Output is correct
5 Correct 13 ms 24788 KB Output is correct
6 Correct 13 ms 25000 KB Output is correct
7 Correct 14 ms 24760 KB Output is correct
8 Correct 11 ms 24916 KB Output is correct
9 Correct 16 ms 24996 KB Output is correct
10 Correct 14 ms 24992 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 75424 KB Output is correct
2 Correct 831 ms 102712 KB Output is correct
3 Correct 924 ms 120060 KB Output is correct
4 Correct 983 ms 124440 KB Output is correct
5 Correct 943 ms 124044 KB Output is correct
6 Correct 866 ms 122476 KB Output is correct
7 Correct 811 ms 118800 KB Output is correct
8 Correct 1677 ms 117912 KB Output is correct
9 Correct 1710 ms 124272 KB Output is correct
10 Correct 692 ms 122164 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24536 KB Output is correct
2 Correct 15 ms 24844 KB Output is correct
3 Correct 15 ms 25076 KB Output is correct
4 Correct 12 ms 24572 KB Output is correct
5 Correct 13 ms 24788 KB Output is correct
6 Correct 13 ms 25000 KB Output is correct
7 Correct 14 ms 24760 KB Output is correct
8 Correct 11 ms 24916 KB Output is correct
9 Correct 16 ms 24996 KB Output is correct
10 Correct 14 ms 24992 KB Output is correct
11 Correct 15 ms 25000 KB Output is correct
12 Correct 19 ms 25560 KB Output is correct
13 Correct 17 ms 25556 KB Output is correct
14 Correct 16 ms 25352 KB Output is correct
15 Correct 21 ms 25912 KB Output is correct
16 Correct 17 ms 25656 KB Output is correct
17 Correct 16 ms 25576 KB Output is correct
18 Correct 15 ms 26324 KB Output is correct
19 Correct 13 ms 25560 KB Output is correct
20 Correct 14 ms 25556 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24536 KB Output is correct
2 Correct 15 ms 24844 KB Output is correct
3 Correct 15 ms 25076 KB Output is correct
4 Correct 12 ms 24572 KB Output is correct
5 Correct 13 ms 24788 KB Output is correct
6 Correct 13 ms 25000 KB Output is correct
7 Correct 14 ms 24760 KB Output is correct
8 Correct 11 ms 24916 KB Output is correct
9 Correct 16 ms 24996 KB Output is correct
10 Correct 14 ms 24992 KB Output is correct
11 Correct 15 ms 25000 KB Output is correct
12 Correct 19 ms 25560 KB Output is correct
13 Correct 17 ms 25556 KB Output is correct
14 Correct 16 ms 25352 KB Output is correct
15 Correct 21 ms 25912 KB Output is correct
16 Correct 17 ms 25656 KB Output is correct
17 Correct 16 ms 25576 KB Output is correct
18 Correct 15 ms 26324 KB Output is correct
19 Correct 13 ms 25560 KB Output is correct
20 Correct 14 ms 25556 KB Output is correct
21 Correct 30 ms 29036 KB Output is correct
22 Correct 35 ms 31732 KB Output is correct
23 Correct 42 ms 33640 KB Output is correct
24 Correct 44 ms 32692 KB Output is correct
25 Correct 27 ms 30848 KB Output is correct
26 Correct 52 ms 33600 KB Output is correct
27 Correct 45 ms 33848 KB Output is correct
28 Correct 79 ms 34208 KB Output is correct
29 Correct 51 ms 32800 KB Output is correct
30 Correct 56 ms 35316 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24536 KB Output is correct
2 Correct 15 ms 24844 KB Output is correct
3 Correct 15 ms 25076 KB Output is correct
4 Correct 12 ms 24572 KB Output is correct
5 Correct 13 ms 24788 KB Output is correct
6 Correct 13 ms 25000 KB Output is correct
7 Correct 14 ms 24760 KB Output is correct
8 Correct 11 ms 24916 KB Output is correct
9 Correct 16 ms 24996 KB Output is correct
10 Correct 14 ms 24992 KB Output is correct
11 Correct 288 ms 75424 KB Output is correct
12 Correct 831 ms 102712 KB Output is correct
13 Correct 924 ms 120060 KB Output is correct
14 Correct 983 ms 124440 KB Output is correct
15 Correct 943 ms 124044 KB Output is correct
16 Correct 866 ms 122476 KB Output is correct
17 Correct 811 ms 118800 KB Output is correct
18 Correct 1677 ms 117912 KB Output is correct
19 Correct 1710 ms 124272 KB Output is correct
20 Correct 692 ms 122164 KB Output is correct
21 Correct 15 ms 25000 KB Output is correct
22 Correct 19 ms 25560 KB Output is correct
23 Correct 17 ms 25556 KB Output is correct
24 Correct 16 ms 25352 KB Output is correct
25 Correct 21 ms 25912 KB Output is correct
26 Correct 17 ms 25656 KB Output is correct
27 Correct 16 ms 25576 KB Output is correct
28 Correct 15 ms 26324 KB Output is correct
29 Correct 13 ms 25560 KB Output is correct
30 Correct 14 ms 25556 KB Output is correct
31 Correct 30 ms 29036 KB Output is correct
32 Correct 35 ms 31732 KB Output is correct
33 Correct 42 ms 33640 KB Output is correct
34 Correct 44 ms 32692 KB Output is correct
35 Correct 27 ms 30848 KB Output is correct
36 Correct 52 ms 33600 KB Output is correct
37 Correct 45 ms 33848 KB Output is correct
38 Correct 79 ms 34208 KB Output is correct
39 Correct 51 ms 32800 KB Output is correct
40 Correct 56 ms 35316 KB Output is correct
41 Correct 193 ms 65736 KB Output is correct
42 Correct 609 ms 94944 KB Output is correct
43 Correct 308 ms 84636 KB Output is correct
44 Correct 1150 ms 115832 KB Output is correct
45 Correct 994 ms 110412 KB Output is correct
46 Correct 639 ms 107460 KB Output is correct
47 Correct 998 ms 108908 KB Output is correct
48 Correct 682 ms 104128 KB Output is correct
49 Correct 533 ms 116288 KB Output is correct
50 Correct 702 ms 115124 KB Output is correct
51 Correct 369 ms 78960 KB Output is correct
52 Correct 894 ms 98224 KB Output is correct
53 Correct 724 ms 104716 KB Output is correct
54 Correct 1404 ms 105756 KB Output is correct
55 Correct 1646 ms 112876 KB Output is correct