oj.uz

Submission #592878

# Submission time Handle Problem Language Result Execution time Memory
592878 2022-07-09T17:26:15 Z MohamedFaresNebili Parachute rings (IOI12_rings) C++14
100 / 100
 1829 ms 262144 KB 
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound

                int N, P[1000001], C[1000001];
                int K[1000001], S[1000001];
                vector<int> adj[1000001], R;
                bool vis[1000001];
                set<int> res;

                int findSet(int v) {
                    if(P[v] == v) return v;
                    return P[v] = findSet(P[v]);
                }
                void unionSet(int u, int v) {
                    u = findSet(u), v = findSet(v);
                    if(u == v) return;
                    P[v] = u; S[u] += S[v];
                }
                void Init(int n) {
                    N = n;
                    for(int l = 0; l < N; l++)
                        P[l] = l, res.insert(l);
                }
                void solve(set<int> cur) {
                    int i = 0;
                    for(auto u : cur) {
                        if(res.count(u))
                            K[i++] = u;
                    }
                    res.clear();
                    for(int l = 0; l < i; l++)
                        res.insert(K[l]);
                }
                bool dfs(int v, int p, int d) {
                    C[v] = p; vis[v] = 1;
                    R.push_back(v);
                    if(v == d) {
                        set<int> cur;
                        cur.insert(v); v = C[v];
                        while(v != d) {
                            cur.insert(v); v = C[v];
                        }
                        solve(cur);
                        return 1;
                    }
                    for(auto u : adj[v]) {
                        if(u == p || vis[u]) continue;
                        if(dfs(u, v, d)) return 1;
                    }
                    return 0;
                }
                void Link(int A, int B) {
                    int U = findSet(A), V = findSet(B);
                    adj[A].push_back(B);
                    adj[B].push_back(A);

                    if(U == V) {
                        S[U]++;
                        if(S[U] <= 3) dfs(A, B, B);
                        for(auto u : R) vis[u] = 0;
                        R.clear();

                        if(S[U] == 2) {
                            set<int> New;
                            auto it = res.begin();
                            while(it != res.end()) {
                                if(adj[*it].size() >= 3)
                                    New.insert(*it);
                                it++;
                            }
                            res.clear(); swap(New, res);
                        }

                    }
                    else unionSet(U, V);

                    set<int> New;
                    if(adj[A].size() == 4)
                        New.clear(), New.insert(A), solve(New);
                    if(adj[B].size() == 4)
                        New.clear(), New.insert(B), solve(New);
                    if(adj[A].size() == 3) {
                        New.clear(); New.insert(A);
                        for(auto u : adj[A])
                            New.insert(u);
                        solve(New);
                    }
                    if(adj[B].size() == 3) {
                        New.clear(); New.insert(B);
                        for(auto u : adj[B])
                            New.insert(u);
                        solve(New);
                    }
                }
                int CountCritical() {
                    return res.size();
                }

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24116 KB Output is correct
3 Correct 14 ms 24148 KB Output is correct
4 Correct 14 ms 23892 KB Output is correct
5 Correct 14 ms 24532 KB Output is correct
6 Correct 16 ms 25456 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 15 ms 24276 KB Output is correct
9 Correct 15 ms 24196 KB Output is correct
10 Correct 14 ms 24276 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 68500 KB Output is correct
2 Correct 898 ms 81568 KB Output is correct
3 Correct 1230 ms 84144 KB Output is correct
4 Correct 1090 ms 112432 KB Output is correct
5 Correct 1118 ms 120512 KB Output is correct
6 Correct 1829 ms 262144 KB Output is correct
7 Correct 1203 ms 96248 KB Output is correct
8 Correct 1072 ms 114020 KB Output is correct
9 Correct 1142 ms 122384 KB Output is correct
10 Correct 1539 ms 140712 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24116 KB Output is correct
3 Correct 14 ms 24148 KB Output is correct
4 Correct 14 ms 23892 KB Output is correct
5 Correct 14 ms 24532 KB Output is correct
6 Correct 16 ms 25456 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 15 ms 24276 KB Output is correct
9 Correct 15 ms 24196 KB Output is correct
10 Correct 14 ms 24276 KB Output is correct
11 Correct 14 ms 24292 KB Output is correct
12 Correct 17 ms 24976 KB Output is correct
13 Correct 17 ms 24916 KB Output is correct
14 Correct 17 ms 24396 KB Output is correct
15 Correct 18 ms 24968 KB Output is correct
16 Correct 19 ms 24844 KB Output is correct
17 Correct 19 ms 24584 KB Output is correct
18 Correct 20 ms 25024 KB Output is correct
19 Correct 18 ms 24788 KB Output is correct
20 Correct 17 ms 24672 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24116 KB Output is correct
3 Correct 14 ms 24148 KB Output is correct
4 Correct 14 ms 23892 KB Output is correct
5 Correct 14 ms 24532 KB Output is correct
6 Correct 16 ms 25456 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 15 ms 24276 KB Output is correct
9 Correct 15 ms 24196 KB Output is correct
10 Correct 14 ms 24276 KB Output is correct
11 Correct 14 ms 24292 KB Output is correct
12 Correct 17 ms 24976 KB Output is correct
13 Correct 17 ms 24916 KB Output is correct
14 Correct 17 ms 24396 KB Output is correct
15 Correct 18 ms 24968 KB Output is correct
16 Correct 19 ms 24844 KB Output is correct
17 Correct 19 ms 24584 KB Output is correct
18 Correct 20 ms 25024 KB Output is correct
19 Correct 18 ms 24788 KB Output is correct
20 Correct 17 ms 24672 KB Output is correct
21 Correct 43 ms 27552 KB Output is correct
22 Correct 50 ms 29772 KB Output is correct
23 Correct 60 ms 31292 KB Output is correct
24 Correct 76 ms 29516 KB Output is correct
25 Correct 46 ms 29508 KB Output is correct
26 Correct 65 ms 29808 KB Output is correct
27 Correct 86 ms 31140 KB Output is correct
28 Correct 65 ms 29268 KB Output is correct
29 Correct 60 ms 29604 KB Output is correct
30 Correct 89 ms 36264 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24116 KB Output is correct
3 Correct 14 ms 24148 KB Output is correct
4 Correct 14 ms 23892 KB Output is correct
5 Correct 14 ms 24532 KB Output is correct
6 Correct 16 ms 25456 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 15 ms 24276 KB Output is correct
9 Correct 15 ms 24196 KB Output is correct
10 Correct 14 ms 24276 KB Output is correct
11 Correct 455 ms 68500 KB Output is correct
12 Correct 898 ms 81568 KB Output is correct
13 Correct 1230 ms 84144 KB Output is correct
14 Correct 1090 ms 112432 KB Output is correct
15 Correct 1118 ms 120512 KB Output is correct
16 Correct 1829 ms 262144 KB Output is correct
17 Correct 1203 ms 96248 KB Output is correct
18 Correct 1072 ms 114020 KB Output is correct
19 Correct 1142 ms 122384 KB Output is correct
20 Correct 1539 ms 140712 KB Output is correct
21 Correct 14 ms 24292 KB Output is correct
22 Correct 17 ms 24976 KB Output is correct
23 Correct 17 ms 24916 KB Output is correct
24 Correct 17 ms 24396 KB Output is correct
25 Correct 18 ms 24968 KB Output is correct
26 Correct 19 ms 24844 KB Output is correct
27 Correct 19 ms 24584 KB Output is correct
28 Correct 20 ms 25024 KB Output is correct
29 Correct 18 ms 24788 KB Output is correct
30 Correct 17 ms 24672 KB Output is correct
31 Correct 43 ms 27552 KB Output is correct
32 Correct 50 ms 29772 KB Output is correct
33 Correct 60 ms 31292 KB Output is correct
34 Correct 76 ms 29516 KB Output is correct
35 Correct 46 ms 29508 KB Output is correct
36 Correct 65 ms 29808 KB Output is correct
37 Correct 86 ms 31140 KB Output is correct
38 Correct 65 ms 29268 KB Output is correct
39 Correct 60 ms 29604 KB Output is correct
40 Correct 89 ms 36264 KB Output is correct
41 Correct 283 ms 63324 KB Output is correct
42 Correct 587 ms 89224 KB Output is correct
43 Correct 462 ms 83248 KB Output is correct
44 Correct 830 ms 91608 KB Output is correct
45 Correct 998 ms 107168 KB Output is correct
46 Correct 1123 ms 110108 KB Output is correct
47 Correct 1356 ms 195800 KB Output is correct
48 Correct 680 ms 87184 KB Output is correct
49 Correct 814 ms 114604 KB Output is correct
50 Correct 833 ms 113352 KB Output is correct
51 Correct 430 ms 75596 KB Output is correct
52 Correct 673 ms 78780 KB Output is correct
53 Correct 673 ms 86036 KB Output is correct
54 Correct 936 ms 98508 KB Output is correct
55 Correct 977 ms 84760 KB Output is correct