oj.uz

Submission #494780

# Submission time Handle Problem Language Result Execution time Memory
494780 2021-12-16T09:13:51 Z abc864197532 Parachute rings (IOI12_rings) C++17
37 / 100
 2288 ms 119296 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define X first
#define Y second
#define pii pair<int, int>
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
    cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args);
#include "grader_B.cpp"
#else
#define test(args...) void(0);
#endif
const int N = 1000000;

vector <pii> edge;
vector <int> adj[N];
int deg[N], n, mx, id[N];
bool grt, dead[4];

struct Dsu {
    int dsu[N], sz[N];
    bool cyc;
    
    void init(int n) {
        iota(dsu, dsu + n, 0);
        fill(sz, sz + n, 1);
        cyc = false;
    }

    int Find(int x) {
        if (dsu[x] == x)
            return x;
        return dsu[x] = Find(dsu[x]);
    }
    bool Union(int u, int v) {
        u = Find(u), v = Find(v);
        if (u == v)
            return cyc = true;
        dsu[u] = v;
        sz[v] += sz[u];
        return false;
    }
} ord, p[4];

void Init(int N) {
    n = mx = N;
    ord.init(n);
    for (int i : {0, 1, 2, 3})
        p[i].init(n);
}

void gen(int v) {
    assert(deg[v] == 3);
    id[0] = v;
    for (int i : {1, 2, 3})
        id[i] = adj[v][i - 1];
    for (int i = 0; i < 4; ++i) {
        int v = id[i];
        for (pii A : edge) {
            if (A.X != v && A.Y != v) {
                p[i].Union(A.X, A.Y);
            }
        }
    }
}

void upd(int v) {
    if (deg[v] == 3) {
        for (int i = 0; i < 4; ++i) {
            bool is = (v == id[i]);
            for (int u : adj[v]) 
                if (u == id[i])
                    is = true;
            dead[i] = !is;
        }
    } else {
        for (int i = 0; i < 4; ++i) if (id[i] != v)
            dead[i] = true;
    }
}

void Link(int a, int b) {
    deg[a]++, deg[b]++;
    adj[a].pb(b), adj[b].pb(a);
    if (deg[a] >= 3) {
        if (!grt)
            gen(a), grt = true;
        else
            upd(a);
    }
    if (deg[b] >= 3) {
        if (!grt)
            gen(b), grt = true;
        else
            upd(b);
    }
    if (grt) {
        for (int i = 0; i < 4; ++i) if (a != id[i] && b != id[i]) {
            p[i].Union(a, b);
        }
    } else {
        edge.eb(a, b);
        if (ord.Union(a, b)) {
            if (mx == n)
                mx = ord.sz[ord.Find(a)];
            else
                mx = 0;
        }
    }
}

int CountCritical() {
    if (grt) {
        int ans = 0;
        for (int i = 0; i < 4; ++i) if (!dead[i])
            ans += !p[i].cyc;
        return ans;
    } else {
        return mx;
    }
}

/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23996 KB Output is correct
2 Correct 20 ms 24212 KB Output is correct
3 Correct 16 ms 24336 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 14 ms 24144 KB Output is correct
6 Correct 15 ms 24400 KB Output is correct
7 Correct 14 ms 24048 KB Output is correct
8 Correct 16 ms 24192 KB Output is correct
9 Correct 15 ms 24348 KB Output is correct
10 Correct 15 ms 24312 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 73588 KB Output is correct
2 Correct 1303 ms 96052 KB Output is correct
3 Correct 2288 ms 106968 KB Output is correct
4 Correct 1090 ms 119292 KB Output is correct
5 Correct 1132 ms 119296 KB Output is correct
6 Correct 1016 ms 117524 KB Output is correct
7 Correct 1895 ms 105832 KB Output is correct
8 Correct 1437 ms 110908 KB Output is correct
9 Correct 1453 ms 117916 KB Output is correct
10 Correct 769 ms 116772 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23996 KB Output is correct
2 Correct 20 ms 24212 KB Output is correct
3 Correct 16 ms 24336 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 14 ms 24144 KB Output is correct
6 Correct 15 ms 24400 KB Output is correct
7 Correct 14 ms 24048 KB Output is correct
8 Correct 16 ms 24192 KB Output is correct
9 Correct 15 ms 24348 KB Output is correct
10 Correct 15 ms 24312 KB Output is correct
11 Correct 15 ms 24264 KB Output is correct
12 Correct 17 ms 24784 KB Output is correct
13 Incorrect 25 ms 24784 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23996 KB Output is correct
2 Correct 20 ms 24212 KB Output is correct
3 Correct 16 ms 24336 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 14 ms 24144 KB Output is correct
6 Correct 15 ms 24400 KB Output is correct
7 Correct 14 ms 24048 KB Output is correct
8 Correct 16 ms 24192 KB Output is correct
9 Correct 15 ms 24348 KB Output is correct
10 Correct 15 ms 24312 KB Output is correct
11 Correct 15 ms 24264 KB Output is correct
12 Correct 17 ms 24784 KB Output is correct
13 Incorrect 25 ms 24784 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23996 KB Output is correct
2 Correct 20 ms 24212 KB Output is correct
3 Correct 16 ms 24336 KB Output is correct
4 Correct 13 ms 23924 KB Output is correct
5 Correct 14 ms 24144 KB Output is correct
6 Correct 15 ms 24400 KB Output is correct
7 Correct 14 ms 24048 KB Output is correct
8 Correct 16 ms 24192 KB Output is correct
9 Correct 15 ms 24348 KB Output is correct
10 Correct 15 ms 24312 KB Output is correct
11 Correct 459 ms 73588 KB Output is correct
12 Correct 1303 ms 96052 KB Output is correct
13 Correct 2288 ms 106968 KB Output is correct
14 Correct 1090 ms 119292 KB Output is correct
15 Correct 1132 ms 119296 KB Output is correct
16 Correct 1016 ms 117524 KB Output is correct
17 Correct 1895 ms 105832 KB Output is correct
18 Correct 1437 ms 110908 KB Output is correct
19 Correct 1453 ms 117916 KB Output is correct
20 Correct 769 ms 116772 KB Output is correct
21 Correct 15 ms 24264 KB Output is correct
22 Correct 17 ms 24784 KB Output is correct
23 Incorrect 25 ms 24784 KB Output isn't correct
24 Halted 0 ms 0 KB -