oj.uz

Submission #1111726

# Submission time Handle Problem Language Result Execution time Memory
1111726 2024-11-12T18:19:07 Z vjudge1 Parachute rings (IOI12_rings) C++17
17 / 100
 770 ms 119408 KB 
#include <bits/stdc++.h>
using namespace std;

#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

#define ll long long
#define pii pair<int, int>

#define fi first
#define se second

const int nmax = 1e6 + 5;

int theta, n, q;
int u, v, cyc, res;
bool check = false;

int par[nmax], sz[nmax], deg[nmax];
vector<pii> edges;
vector<int> adj[nmax];

struct DSU {
    int root, ans;
    vector<int> par, deg;

    DSU() {
        ans = 1;
        root = 0;
        par.resize(nmax + 1);
        deg.resize(nmax + 1);
        for (int i = 1; i <= nmax; i++) {
            par[i] = i;
            deg[i] = 0;
        }
    }

    void init() {
        ans = 1;
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            // deg[i] = 0;
        }
        for (auto [u, v] : edges) {
            merge(u, v);
        }
    }

    int find(int u) {
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }
    
    void merge(int u, int v) {
        if (u == root || v == root || ans == 0) return;
        if (++deg[u] == 3) ans = 0;
        if (++deg[v] == 3) ans = 0;

        u = find(u), v = find(v);
        if (u == v) {
            ans = 0;
            return;
        }
        par[u] = v;
    }
} ds[4];

int find(int u) {
    if (u == par[u]) return u;
    return par[u] = find(par[u]);
}

void Init(int _n) {
    n = _n;
    for (int i = 1; i <= n; i++) {
        par[i] = i;
        deg[i] = 0;
        sz[i] = 1;
    }
}

void Link(int u, int v) {
    if (check) {
        for (int i = 0; i < 4; i++)
            ds[i].merge(u, v);
        return;
    }
    edges.push_back({u, v});
    adj[u].push_back(v);
    adj[v].push_back(u);
    
    if (deg[u] == 2 || deg[v] == 2) check = true;

    if (++deg[u] == 3) {
        ds[0].root = u;
        for (int i = 1; i < 4; i++) ds[i].root = adj[u][i - 1];
        for (int i = 0; i < 4; i++) ds[i].init();
        return;
    }

    if (++deg[v] == 3) {
        ds[0].root = v;
        for (int i = 1; i < 4; i++) ds[i].root = adj[v][i - 1];
        for (int i = 0; i < 4; i++) ds[i].init();
        return;
    }

    u = find(u), v = find(v);
    if (u == v) {
        res = sz[u];
        cyc++;
    } else {
        sz[u] += sz[v];
        par[v] = u;
    }
}

int CountCritical() {
    if (cyc > 1) return 0;
    if (check) return ds[0].ans + ds[1].ans + ds[2].ans + ds[3].ans;
    if (cyc == 1) return res;
    return n;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56400 KB Output is correct
2 Correct 34 ms 56648 KB Output is correct
3 Correct 34 ms 56656 KB Output is correct
4 Correct 42 ms 56396 KB Output is correct
5 Correct 39 ms 56656 KB Output is correct
6 Incorrect 41 ms 56912 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 88144 KB Output is correct
2 Correct 324 ms 82360 KB Output is correct
3 Correct 182 ms 77384 KB Output is correct
4 Correct 770 ms 119316 KB Output is correct
5 Correct 752 ms 119408 KB Output is correct
6 Correct 696 ms 117668 KB Output is correct
7 Correct 166 ms 67656 KB Output is correct
8 Correct 562 ms 98100 KB Output is correct
9 Correct 728 ms 117184 KB Output is correct
10 Correct 574 ms 116856 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56400 KB Output is correct
2 Correct 34 ms 56648 KB Output is correct
3 Correct 34 ms 56656 KB Output is correct
4 Correct 42 ms 56396 KB Output is correct
5 Correct 39 ms 56656 KB Output is correct
6 Incorrect 41 ms 56912 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56400 KB Output is correct
2 Correct 34 ms 56648 KB Output is correct
3 Correct 34 ms 56656 KB Output is correct
4 Correct 42 ms 56396 KB Output is correct
5 Correct 39 ms 56656 KB Output is correct
6 Incorrect 41 ms 56912 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56400 KB Output is correct
2 Correct 34 ms 56648 KB Output is correct
3 Correct 34 ms 56656 KB Output is correct
4 Correct 42 ms 56396 KB Output is correct
5 Correct 39 ms 56656 KB Output is correct
6 Incorrect 41 ms 56912 KB Output isn't correct
7 Halted 0 ms 0 KB -