oj.uz

Submission #382343

# Submission time Handle Problem Language Result Execution time Memory
382343 2021-03-27T06:40:17 Z ParsaAlizadeh Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 73152 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;

#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

constexpr ll pw(ll a, ll b, ll mod) {
    return (!b    ? 1 :
            b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
                    pw(a * a % mod, b / 2, mod));
}

constexpr int N   = 1e6 + 10;

int n, mark[N], par[N], edg[N], sz[N];
vector<int> adj[N];

bool critDFS(int u) {
    int d = 0;
    bool flag = true;
    mark[u] = 1;
    for (int v : adj[u]) if (mark[v] < 3) {
        d++;
        flag &= (mark[v] != 2);
        if (mark[v] == 0) {
            flag &= critDFS(v);
        }
    }
    flag &= (d <= 2);
    mark[u] = 2;
    return flag;
}

bool check(int u) {
    bool flag = true;
    fill(mark, mark + N, 0);
    mark[u] = 3;
    for (int i = 0; i < n; i++) if (mark[i] == 0) {
        flag &= critDFS(i);
    }
    return flag;
}

int dsufind(int u) {
    return (par[u] == -1 ? u : par[u] = dsufind(par[u]));
}

void dsumerge(int u, int v) {
    u = dsufind(u), v = dsufind(v);
    if (u == v) {
        edg[u]++;
        return;
    }
    if (sz[v] > sz[u])
        swap(u, v);
    par[v] = u;
    edg[u] += edg[v] + 1;
    sz[u] += sz[v];
}

void Init(int N_) {
    n = N_;
    assert(n < N);
    fill(par, par + n, -1);
    fill(sz, sz + n, 1);
}

void Link(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);

    dsumerge(u, v);
}

int CountCritical() {
    vector<int> v3, v4;
    for (int i = 0; i < n; i++) {
        if (adj[i].size() >= 4)
            v4.push_back(i);
        else if (adj[i].size() == 3)
            v3.push_back(i);
    }
    if (v4.size() >= 2)
        return 0;
    if (v4.size() == 1)
        return check(v4[0]);
    if (v3.size() >= 1) {
        int ans = check(v3[0]);
        for (int v : adj[v3[0]])
            ans += check(v);
        return ans;
    }
    int t[2] = {0, 0};
    for (int i = 0; i < n; i++) if (dsufind(i) == i) {
        if (edg[i] == sz[i]) {
            if (t[1] > 0) return 0;
            t[1] = sz[i];
        }
        else
            t[0] += sz[i];
    }
    return (t[1] > 0 ? t[1] : t[0]);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 22 ms 28012 KB Output is correct
3 Correct 22 ms 28012 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 19 ms 23916 KB Output is correct
6 Correct 19 ms 24044 KB Output is correct
7 Correct 23 ms 27884 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 26 ms 28012 KB Output is correct
10 Correct 26 ms 28012 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 46832 KB Output is correct
2 Correct 1101 ms 63468 KB Output is correct
3 Correct 1010 ms 65276 KB Output is correct
4 Correct 1126 ms 67820 KB Output is correct
5 Correct 1148 ms 68332 KB Output is correct
6 Correct 1103 ms 67088 KB Output is correct
7 Correct 962 ms 65248 KB Output is correct
8 Correct 2007 ms 69760 KB Output is correct
9 Correct 2173 ms 73152 KB Output is correct
10 Correct 722 ms 62700 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 22 ms 28012 KB Output is correct
3 Correct 22 ms 28012 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 19 ms 23916 KB Output is correct
6 Correct 19 ms 24044 KB Output is correct
7 Correct 23 ms 27884 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 26 ms 28012 KB Output is correct
10 Correct 26 ms 28012 KB Output is correct
11 Correct 148 ms 28012 KB Output is correct
12 Correct 67 ms 28268 KB Output is correct
13 Correct 224 ms 28396 KB Output is correct
14 Correct 121 ms 28140 KB Output is correct
15 Correct 155 ms 28268 KB Output is correct
16 Correct 29 ms 24428 KB Output is correct
17 Correct 545 ms 28268 KB Output is correct
18 Correct 111 ms 28524 KB Output is correct
19 Correct 30 ms 24420 KB Output is correct
20 Correct 251 ms 28396 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 22 ms 28012 KB Output is correct
3 Correct 22 ms 28012 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 19 ms 23916 KB Output is correct
6 Correct 19 ms 24044 KB Output is correct
7 Correct 23 ms 27884 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 26 ms 28012 KB Output is correct
10 Correct 26 ms 28012 KB Output is correct
11 Correct 148 ms 28012 KB Output is correct
12 Correct 67 ms 28268 KB Output is correct
13 Correct 224 ms 28396 KB Output is correct
14 Correct 121 ms 28140 KB Output is correct
15 Correct 155 ms 28268 KB Output is correct
16 Correct 29 ms 24428 KB Output is correct
17 Correct 545 ms 28268 KB Output is correct
18 Correct 111 ms 28524 KB Output is correct
19 Correct 30 ms 24420 KB Output is correct
20 Correct 251 ms 28396 KB Output is correct
21 Execution timed out 4067 ms 25852 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 22 ms 28012 KB Output is correct
3 Correct 22 ms 28012 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 19 ms 23916 KB Output is correct
6 Correct 19 ms 24044 KB Output is correct
7 Correct 23 ms 27884 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 26 ms 28012 KB Output is correct
10 Correct 26 ms 28012 KB Output is correct
11 Correct 460 ms 46832 KB Output is correct
12 Correct 1101 ms 63468 KB Output is correct
13 Correct 1010 ms 65276 KB Output is correct
14 Correct 1126 ms 67820 KB Output is correct
15 Correct 1148 ms 68332 KB Output is correct
16 Correct 1103 ms 67088 KB Output is correct
17 Correct 962 ms 65248 KB Output is correct
18 Correct 2007 ms 69760 KB Output is correct
19 Correct 2173 ms 73152 KB Output is correct
20 Correct 722 ms 62700 KB Output is correct
21 Correct 148 ms 28012 KB Output is correct
22 Correct 67 ms 28268 KB Output is correct
23 Correct 224 ms 28396 KB Output is correct
24 Correct 121 ms 28140 KB Output is correct
25 Correct 155 ms 28268 KB Output is correct
26 Correct 29 ms 24428 KB Output is correct
27 Correct 545 ms 28268 KB Output is correct
28 Correct 111 ms 28524 KB Output is correct
29 Correct 30 ms 24420 KB Output is correct
30 Correct 251 ms 28396 KB Output is correct
31 Execution timed out 4067 ms 25852 KB Time limit exceeded
32 Halted 0 ms 0 KB -