oj.uz

Submission #1077037

# Submission time Handle Problem Language Result Execution time Memory
1077037 2024-08-26T21:33:25 Z ArthuroWich Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 119632 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000005], vis;
int n, p[1000005], s[1000005];
bool f = 1;
int find(int x) {
    if (p[x] == x) {
        return x;
    }
    p[x] = find(p[x]);
    return p[x];
}
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) {
        return;
    }
    if (s[b] > s[a]) {
        swap(a, b);
    }
    s[a] += s[b];
    p[b] = a;
}
set<int> st;
void Init(int N_) {
    n = N_;
    for (int i = 0; i < n; i++) {
        st.insert(i);
        p[i] = i;
        s[i] = 1;
    }
}
void dfs(int i, int p, int s) {
    if (vis[i]) {
        f = 0;
        return;
    }
    vis[i] = 1;
    for (int j : adj[i]) {
        if (j == p || j == s) {
            continue;
        }
        dfs(j, i, s);
    }
}
int calc(int a) {
    vis.resize(n, 0);
    vector<int> co(n, 0);
    for (int j : adj[a]) {
        co[j]++;
    }
    f = 1;
    for (int i = 0; i < n; i++) {
        if (i != a && adj[i].size()-co[i] > 2) {
            f = 0;
            break;
        }
        if (vis[i] || i == a) {
            continue;
        }
        dfs(i, -1, a);
    }
    vis.clear();
    return f;
}
int le = -1, pre[1000005];
void dfscyc(int i, int p) {
    if (le != -1) {
        return;
    }
    if (vis[i]) {
        set<int> b;
        pre[i] = p;
        int a = i;
        le = 0;
        a = pre[a];
        if (st.count(a)) {
            if (calc(a)) {
                b.insert(a);
            }
        }
        while(a != i) {
            a = pre[a];
            if (st.count(a)) {
                if (calc(a)) {
                    b.insert(a);
                }
            }
        }
        st = b;
        return;
    }
    vis[i] = 1;
    pre[i] = p;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfscyc(j, i);
    }
}
void cycle(int a) {
    vis.resize(n, 0);
    le = -1;
    dfscyc(a, 0);
    vis.clear();
}
bool cyc = 1, cant = 0;
int s4 = -1;
void Link(int A, int B) {
    adj[A].push_back(B);
    adj[B].push_back(A);
    if (cant || st.size() == 0) {
        return;
    }
    if (find(A) == find(B)) {
        cycle(A);
    }
    if (find(A) != find(B)) {
        merge(A, B);
    }
    if (adj[A].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = A;
        if (st.count(A) && calc(A)) {
            st = {A};
        } else {
            st = {};
        }
    }
    if (adj[B].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = B;
        if (st.count(B) && calc(B)) {
            st = {B};
        } else {
            st = {};
        }
    }
    if (adj[A].size() >= 4 && s4 != -1 && s4 != A) {
        st.clear();
        cant = 1;
        return;
    }
    if (adj[B].size() >= 4 && s4 != -1 && s4 != B) {
        st.clear();
        cant = 1;
        return;
    }
    if (adj[A].size() == 3) {
        set<int> b;
        if (st.count(A)) {
            b.insert(A);
        }
        for (int j : adj[A]) {
            if (st.count(j)) {
                b.insert(j);
            }
        }
        st = b;
    }
    if (adj[B].size() == 3) {
        set<int> b;
        if (st.count(B)) {
            b.insert(B);
        }
        for (int j : adj[B]) {
            if (st.count(j)) {
                b.insert(j);
            }
        }
        st = b;
    }
}
int CountCritical() {
    return st.size();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 13 ms 25552 KB Output is correct
3 Correct 10 ms 25436 KB Output is correct
4 Correct 10 ms 25180 KB Output is correct
5 Correct 70 ms 25884 KB Output is correct
6 Correct 236 ms 26452 KB Output is correct
7 Correct 9 ms 25432 KB Output is correct
8 Correct 11 ms 25692 KB Output is correct
9 Correct 10 ms 25668 KB Output is correct
10 Correct 10 ms 25692 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 69968 KB Output is correct
2 Correct 629 ms 82744 KB Output is correct
3 Correct 569 ms 79188 KB Output is correct
4 Execution timed out 4017 ms 119632 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 13 ms 25552 KB Output is correct
3 Correct 10 ms 25436 KB Output is correct
4 Correct 10 ms 25180 KB Output is correct
5 Correct 70 ms 25884 KB Output is correct
6 Correct 236 ms 26452 KB Output is correct
7 Correct 9 ms 25432 KB Output is correct
8 Correct 11 ms 25692 KB Output is correct
9 Correct 10 ms 25668 KB Output is correct
10 Correct 10 ms 25692 KB Output is correct
11 Incorrect 10 ms 25688 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 13 ms 25552 KB Output is correct
3 Correct 10 ms 25436 KB Output is correct
4 Correct 10 ms 25180 KB Output is correct
5 Correct 70 ms 25884 KB Output is correct
6 Correct 236 ms 26452 KB Output is correct
7 Correct 9 ms 25432 KB Output is correct
8 Correct 11 ms 25692 KB Output is correct
9 Correct 10 ms 25668 KB Output is correct
10 Correct 10 ms 25692 KB Output is correct
11 Incorrect 10 ms 25688 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 13 ms 25552 KB Output is correct
3 Correct 10 ms 25436 KB Output is correct
4 Correct 10 ms 25180 KB Output is correct
5 Correct 70 ms 25884 KB Output is correct
6 Correct 236 ms 26452 KB Output is correct
7 Correct 9 ms 25432 KB Output is correct
8 Correct 11 ms 25692 KB Output is correct
9 Correct 10 ms 25668 KB Output is correct
10 Correct 10 ms 25692 KB Output is correct
11 Correct 286 ms 69968 KB Output is correct
12 Correct 629 ms 82744 KB Output is correct
13 Correct 569 ms 79188 KB Output is correct
14 Execution timed out 4017 ms 119632 KB Time limit exceeded
15 Halted 0 ms 0 KB -