oj.uz

Submission #1077001

# Submission time Handle Problem Language Result Execution time Memory
1077001 2024-08-26T20:27:37 Z ArthuroWich Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 79376 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 = 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 (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) {
        ans = calc(A);
        for (int j : adj[A]) {
            ans += calc(j);
        }
        if (ans == 0) {
            cant = 1;
            return;
        }
    }
    if (adj[B].size() == 3) {
        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 14 ms 23712 KB Output is correct
2 Correct 12 ms 24156 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 13 ms 24012 KB Output is correct
5 Correct 69 ms 24268 KB Output is correct
6 Correct 278 ms 24484 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 205 ms 24248 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 13 ms 24244 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 47820 KB Output is correct
2 Correct 705 ms 64144 KB Output is correct
3 Correct 469 ms 69436 KB Output is correct
4 Execution timed out 4024 ms 79376 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23712 KB Output is correct
2 Correct 12 ms 24156 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 13 ms 24012 KB Output is correct
5 Correct 69 ms 24268 KB Output is correct
6 Correct 278 ms 24484 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 205 ms 24248 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 13 ms 24244 KB Output is correct
11 Correct 14 ms 24152 KB Output is correct
12 Correct 45 ms 24592 KB Output is correct
13 Correct 28 ms 24408 KB Output is correct
14 Correct 783 ms 24360 KB Output is correct
15 Correct 1020 ms 24516 KB Output is correct
16 Correct 2233 ms 24836 KB Output is correct
17 Correct 16 ms 24412 KB Output is correct
18 Correct 17 ms 24504 KB Output is correct
19 Correct 86 ms 24604 KB Output is correct
20 Correct 14 ms 24408 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23712 KB Output is correct
2 Correct 12 ms 24156 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 13 ms 24012 KB Output is correct
5 Correct 69 ms 24268 KB Output is correct
6 Correct 278 ms 24484 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 205 ms 24248 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 13 ms 24244 KB Output is correct
11 Correct 14 ms 24152 KB Output is correct
12 Correct 45 ms 24592 KB Output is correct
13 Correct 28 ms 24408 KB Output is correct
14 Correct 783 ms 24360 KB Output is correct
15 Correct 1020 ms 24516 KB Output is correct
16 Correct 2233 ms 24836 KB Output is correct
17 Correct 16 ms 24412 KB Output is correct
18 Correct 17 ms 24504 KB Output is correct
19 Correct 86 ms 24604 KB Output is correct
20 Correct 14 ms 24408 KB Output is correct
21 Correct 23 ms 25692 KB Output is correct
22 Correct 38 ms 26708 KB Output is correct
23 Correct 33 ms 27480 KB Output is correct
24 Execution timed out 4059 ms 27368 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23712 KB Output is correct
2 Correct 12 ms 24156 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 13 ms 24012 KB Output is correct
5 Correct 69 ms 24268 KB Output is correct
6 Correct 278 ms 24484 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 205 ms 24248 KB Output is correct
9 Correct 13 ms 24156 KB Output is correct
10 Correct 13 ms 24244 KB Output is correct
11 Correct 228 ms 47820 KB Output is correct
12 Correct 705 ms 64144 KB Output is correct
13 Correct 469 ms 69436 KB Output is correct
14 Execution timed out 4024 ms 79376 KB Time limit exceeded
15 Halted 0 ms 0 KB -