oj.uz

Submission #382342

# Submission time Handle Problem Language Result Execution time Memory
382342 2021-03-27T06:39:07 Z ParsaAlizadeh Parachute rings (IOI12_rings) C++17
20 / 100
 18 ms 1004 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   = 5e3 + 10;
constexpr int MOD = 1e9 + 7;
constexpr ll INF  = 1e18;

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 1 ms 492 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1004 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 18 ms 748 KB Output is correct
12 Runtime error 2 ms 876 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 18 ms 748 KB Output is correct
12 Runtime error 2 ms 876 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Runtime error 2 ms 1004 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -