oj.uz

Submission #1077008

# Submission time Handle Problem Language Result Execution time Memory
1077008 2024-08-26T20:34:18 Z ArthuroWich Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 82972 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000005], vis;
int n, ans = 0, 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;
}
void Init(int N_) {
    n = N_;
    ans = n;
    for (int i = 0; i < n; 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]) {
        pre[i] = p;
        int a = i;
        le = 0;
        a = pre[a];
        le += calc(a);
        while(a != i) {
            a = pre[a];
            le += calc(a);
        }
        return;
    }
    vis[i] = 1;
    pre[i] = p;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfscyc(j, i);
    }
}
int cycle(int a) {
    vis.resize(n, 0);
    le = -1;
    dfscyc(a, 0);
    vis.clear();
    if (le == -1) {
        le = 0;
    }
    return le;
}
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) {
        return;
    }
    if (cyc && find(A) == find(B)) {
        ans = cycle(A);
    }
    if (find(A) != find(B)) {
        merge(A, B);
    }
    if (adj[A].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = A;
        ans = calc(A);
    }
    if (adj[B].size() >= 4 && s4 == -1) {
        cyc = 0;
        s4 = B;
        ans = calc(B);
    }
    if (adj[A].size() >= 4 && s4 != -1 && s4 != A) {
        ans = 0;
        cant = 1;
        return;
    }
    if (adj[B].size() >= 4 && s4 != -1 && s4 != B) {
        ans = 0;
        cant = 1;
        return;
    }
    if (adj[A].size() == 3) {
        cyc = 0;
        ans = calc(A);
        for (int j : adj[A]) {
            ans += calc(j);
        }
        if (ans == 0) {
            cant = 1;
            return;
        }
    }
    if (adj[B].size() == 3) {
        cyc = 0;
        ans = calc(B);
        for (int j : adj[B]) {
            ans += calc(j);
        }
        if (ans == 0) {
            cant = 1;
            return;
        }
    }
}
int CountCritical() {
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 70 ms 24264 KB Output is correct
6 Correct 283 ms 24412 KB Output is correct
7 Correct 12 ms 23896 KB Output is correct
8 Correct 204 ms 24152 KB Output is correct
9 Correct 12 ms 24028 KB Output is correct
10 Correct 14 ms 24156 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 48064 KB Output is correct
2 Correct 642 ms 63852 KB Output is correct
3 Correct 452 ms 72708 KB Output is correct
4 Execution timed out 4066 ms 82972 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 23900 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 70 ms 24264 KB Output is correct
6 Correct 283 ms 24412 KB Output is correct
7 Correct 12 ms 23896 KB Output is correct
8 Correct 204 ms 24152 KB Output is correct
9 Correct 12 ms 24028 KB Output is correct
10 Correct 14 ms 24156 KB Output is correct
11 Incorrect 13 ms 24152 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 70 ms 24264 KB Output is correct
6 Correct 283 ms 24412 KB Output is correct
7 Correct 12 ms 23896 KB Output is correct
8 Correct 204 ms 24152 KB Output is correct
9 Correct 12 ms 24028 KB Output is correct
10 Correct 14 ms 24156 KB Output is correct
11 Incorrect 13 ms 24152 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 12 ms 23900 KB Output is correct
5 Correct 70 ms 24264 KB Output is correct
6 Correct 283 ms 24412 KB Output is correct
7 Correct 12 ms 23896 KB Output is correct
8 Correct 204 ms 24152 KB Output is correct
9 Correct 12 ms 24028 KB Output is correct
10 Correct 14 ms 24156 KB Output is correct
11 Correct 227 ms 48064 KB Output is correct
12 Correct 642 ms 63852 KB Output is correct
13 Correct 452 ms 72708 KB Output is correct
14 Execution timed out 4066 ms 82972 KB Time limit exceeded
15 Halted 0 ms 0 KB -