oj.uz

Submission #1077004

# Submission time Handle Problem Language Result Execution time Memory
1077004 2024-08-26T20:30:46 Z ArthuroWich Parachute rings (IOI12_rings) C++17
0 / 100
 4000 ms 82948 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 f1 = 0, 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 (!f1 && find(A) == find(B)) {
        ans = cycle(A);
    }
    if (find(A) != find(B)) {
        merge(A, B);
    }
    if (adj[A].size() >= 4 && s4 == -1) {
        s4 = A;
        ans = calc(A);
    }
    if (adj[B].size() >= 4 && s4 == -1) {
        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 && s4 != -1) {
        f1 = 1;
        ans = calc(A);
        for (int j : adj[A]) {
            ans += calc(j);
        }
        if (ans == 0) {
            cant = 1;
            return;
        }
    }
    if (adj[B].size() == 3 && s4 != -1) {
        f1 = 1;
        ans = calc(B);
        for (int j : adj[B]) {
            ans += calc(j);
        }
        if (ans == 0) {
            cant = 1;
            return;
        }
    }
}
int CountCritical() {
    return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24232 KB Output is correct
4 Correct 12 ms 23896 KB Output is correct
5 Correct 72 ms 24156 KB Output is correct
6 Correct 267 ms 24556 KB Output is correct
7 Incorrect 11 ms 23900 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 49492 KB Output is correct
2 Correct 505 ms 66636 KB Output is correct
3 Correct 432 ms 72716 KB Output is correct
4 Execution timed out 4014 ms 82948 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24232 KB Output is correct
4 Correct 12 ms 23896 KB Output is correct
5 Correct 72 ms 24156 KB Output is correct
6 Correct 267 ms 24556 KB Output is correct
7 Incorrect 11 ms 23900 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24232 KB Output is correct
4 Correct 12 ms 23896 KB Output is correct
5 Correct 72 ms 24156 KB Output is correct
6 Correct 267 ms 24556 KB Output is correct
7 Incorrect 11 ms 23900 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 12 ms 24232 KB Output is correct
4 Correct 12 ms 23896 KB Output is correct
5 Correct 72 ms 24156 KB Output is correct
6 Correct 267 ms 24556 KB Output is correct
7 Incorrect 11 ms 23900 KB Output isn't correct
8 Halted 0 ms 0 KB -