oj.uz

Submission #1077039

# Submission time Handle Problem Language Result Execution time Memory
1077039 2024-08-26T21:35:49 Z ArthuroWich Parachute rings (IOI12_rings) C++17
0 / 100
 4000 ms 119388 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)) {
            if (calc(A)) {
                b.insert(A);
            }
        }
        for (int j : adj[A]) {
            if (b.size() == 1) {
                continue;
            }
            if (st.count(j)) {
                if (calc(j)) {
                    b.insert(j);
                }
            }
        }
        st = b;
    }
    if (adj[B].size() == 3) {
        set<int> b;
        if (st.count(B)) {
            if (calc(B)) {
                b.insert(B);
            }
        }
        for (int j : adj[B]) {
            if (b.size() == 1) {
                continue;
            }
            if (st.count(j)) {
                if (calc(j)) {
                    b.insert(j);
                }
            }
        }
        st = b;
    }
}
int CountCritical() {
    return st.size();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 12 ms 24172 KB Output is correct
3 Correct 13 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 76 ms 24412 KB Output is correct
6 Correct 303 ms 25096 KB Output is correct
7 Correct 11 ms 25436 KB Output is correct
8 Correct 13 ms 24156 KB Output is correct
9 Incorrect 11 ms 24412 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 68688 KB Output is correct
2 Correct 765 ms 87892 KB Output is correct
3 Correct 702 ms 86852 KB Output is correct
4 Execution timed out 4091 ms 119388 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 12 ms 24172 KB Output is correct
3 Correct 13 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 76 ms 24412 KB Output is correct
6 Correct 303 ms 25096 KB Output is correct
7 Correct 11 ms 25436 KB Output is correct
8 Correct 13 ms 24156 KB Output is correct
9 Incorrect 11 ms 24412 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 12 ms 24172 KB Output is correct
3 Correct 13 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 76 ms 24412 KB Output is correct
6 Correct 303 ms 25096 KB Output is correct
7 Correct 11 ms 25436 KB Output is correct
8 Correct 13 ms 24156 KB Output is correct
9 Incorrect 11 ms 24412 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 12 ms 24172 KB Output is correct
3 Correct 13 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 76 ms 24412 KB Output is correct
6 Correct 303 ms 25096 KB Output is correct
7 Correct 11 ms 25436 KB Output is correct
8 Correct 13 ms 24156 KB Output is correct
9 Incorrect 11 ms 24412 KB Output isn't correct
10 Halted 0 ms 0 KB -