oj.uz

Submission #382361

# Submission time Handle Problem Language Result Execution time Memory
382361 2021-03-27T07:22:24 Z ParsaAlizadeh Parachute rings (IOI12_rings) C++17
0 / 100
 1339 ms 90844 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], sz[N], ans, vgt2;
vector<int> adj[N];
vector<pii> E;

struct TmpDSU {
    int flag = true, u, par[N];

    TmpDSU() {
        fill(par, par + N, -1);
    }

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

    void merge(int u, int v) {
        if (!flag || u == this->u || v == this->u)
            return;
        u = find(u), v = find(v);
        if (u == v) {
            flag = false;
            return;
        }
        if (v < u) swap(u, v);
        this->par[v] = u;
    }
} tmpdsu[4];

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) {
        if (!vgt2)
            ans = (ans > 0 ? 0 : sz[u]);
        return;
    }
    if (sz[v] > sz[u])
        swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
}

void apply(int u) {
    if (adj[u].size() <= 2)
        return;
    if (vgt2) {
        for (int i = 0; i < 4; i++) {
            bool f = tmpdsu[i].u == u;
            if (adj[u].size() == 3)
            for (int v : adj[u])
                f |= tmpdsu[i].u == v;
            tmpdsu[i].flag &= f;
        }
    }
    else {
        vgt2 = 1;
        assert(adj[u].size() == 3);
        tmpdsu[0].u = u;
        for (int i = 0; i < 3; i++)
            tmpdsu[i + 1].u = adj[u][i];
        for (auto &e : E) {
            for (int i = 0; i < 4; i++) 
                tmpdsu[i].merge(e.X, e.Y);
        }
    }
}

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) {
    E.emplace_back(u, v);
    adj[u].push_back(v);
    adj[v].push_back(u);

    if (vgt2)
    for (int i = 0; i < 4; i++) {
        tmpdsu[i].merge(u, v);
    }

    dsumerge(u, v);
    apply(u);
    apply(v);
}

int CountCritical() {
    if (!vgt2)
        return (ans == 0 ? n : ans);
    int t = 0;
    for (int i = 0; i < 4; i++)
        t += tmpdsu[i].flag;
    return t;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 28 ms 39788 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 29 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 27 ms 39532 KB Output is correct
8 Incorrect 29 ms 39788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 68052 KB Output is correct
2 Correct 958 ms 81096 KB Output is correct
3 Correct 1004 ms 85960 KB Output is correct
4 Correct 1076 ms 90312 KB Output is correct
5 Correct 1083 ms 90844 KB Output is correct
6 Correct 1047 ms 89880 KB Output is correct
7 Correct 979 ms 85668 KB Output is correct
8 Correct 1246 ms 87880 KB Output is correct
9 Correct 1339 ms 90804 KB Output is correct
10 Incorrect 739 ms 88648 KB Output isn't correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 28 ms 39788 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 29 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 27 ms 39532 KB Output is correct
8 Incorrect 29 ms 39788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 28 ms 39788 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 29 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 27 ms 39532 KB Output is correct
8 Incorrect 29 ms 39788 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 39532 KB Output is correct
2 Correct 28 ms 39788 KB Output is correct
3 Correct 29 ms 39788 KB Output is correct
4 Correct 29 ms 39532 KB Output is correct
5 Correct 28 ms 39660 KB Output is correct
6 Correct 29 ms 39788 KB Output is correct
7 Correct 27 ms 39532 KB Output is correct
8 Incorrect 29 ms 39788 KB Output isn't correct
9 Halted 0 ms 0 KB -