oj.uz

답안 #589386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589386 2022-07-04T14:28:03 Z TheScrasse 낙하산 고리들 (IOI12_rings) C++14
38 / 100
 4000 ms 213392 KB 
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll int
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e9
#define mod 998244353
#define maxn 1000010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll ms[5], status;
vector<array<ll, 2>> el;

struct graph {
    ll dg[maxn], cn3, cyc, pr[maxn], sz[maxn];
    vector<ll> adj[maxn];

    graph() {
        ll i;
        for (i = 1; i <= n; i++) {
            dg[i] = 0; pr[i] = i; sz[i] = 1;
        }
        cn3 = 0; cyc = 0;
    }

    ll find(ll x) {
        if (x == pr[x]) return x;
        return pr[x] = find(pr[x]);
    }

    bool same(ll a, ll b) {
        return (find(a) == find(b));
    }

    void onion(ll a, ll b) {
        a = find(a); b = find(b);
        if (a == b) {
            cyc++; res = sz[a]; return;
        }
        if (sz[a] < sz[b]) swap(a, b);
        pr[b] = a; sz[a] += sz[b];
    }

    void upd(ll p, ll x) {
        cn3 -= (dg[p] >= 3);
        dg[p] += x;
        cn3 += (dg[p] >= 3);
    }
};

graph gr[5];

void ins(ll p, ll a, ll b) {
    if (ms[p] == a || ms[p] == b) return;
    gr[p].upd(a, 1); gr[p].upd(b, 1);
    gr[p].adj[a].pb(b); gr[p].adj[b].pb(a);
    gr[p].onion(a, b);
}

void Init(int N_) {
    n = N_;
    gr[0] = graph(); gr[1] = graph(); gr[2] = graph(); gr[3] = graph(); gr[4] = graph();
}

void Link(int A, int B) {
    a = A + 1; b = B + 1;
    el.pb({a, b});
    if (status == 0) ins(0, a, b);
    else if (status == 2) ins(1, a, b);
    else for (i = 0; i <= 4; i++) ins(i, a, b);

    if (status == 0) {
        if (gr[0].dg[b] >= 3) swap(a, b);
        if (gr[0].dg[a] >= 3) {
            status = 1;
            ms[1] = a; ms[2] = gr[0].adj[a][0]; ms[3] = gr[0].adj[a][1]; ms[4] = gr[0].adj[a][2];
            gr[1] = graph(); gr[2] = graph(); gr[3] = graph(); gr[4] = graph();
            for (auto [x, y] : el) {
                for (i = 1; i <= 4; i++) ins(i, x, y);
            }
        }
    }

    if (gr[0].dg[a] == 4 || gr[0].dg[b] == 4) status = 2;
}

int CountCritical() {
    // cout << "status =" _ status _ gr[0].cyc << nl;

    if (status == 0) {
        if (gr[0].cyc == 0) return n;
        if (gr[0].cyc == 1) return res;
        return 0;
    }

    res = 0;
    for (i = 1; i <= 4; i++) {
        if (gr[i].cyc + gr[i].cn3 == 0) res++;
    }
    return res;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:82:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |             for (auto [x, y] : el) {
      |                       ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 211592 KB Output is correct
2 Correct 788 ms 212188 KB Output is correct
3 Correct 902 ms 212140 KB Output is correct
4 Correct 289 ms 211684 KB Output is correct
5 Correct 570 ms 211868 KB Output is correct
6 Correct 865 ms 211856 KB Output is correct
7 Correct 262 ms 211844 KB Output is correct
8 Correct 645 ms 211808 KB Output is correct
9 Correct 915 ms 212496 KB Output is correct
10 Correct 912 ms 212500 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4069 ms 212984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 211592 KB Output is correct
2 Correct 788 ms 212188 KB Output is correct
3 Correct 902 ms 212140 KB Output is correct
4 Correct 289 ms 211684 KB Output is correct
5 Correct 570 ms 211868 KB Output is correct
6 Correct 865 ms 211856 KB Output is correct
7 Correct 262 ms 211844 KB Output is correct
8 Correct 645 ms 211808 KB Output is correct
9 Correct 915 ms 212496 KB Output is correct
10 Correct 912 ms 212500 KB Output is correct
11 Correct 927 ms 212492 KB Output is correct
12 Correct 1631 ms 213192 KB Output is correct
13 Correct 1651 ms 213280 KB Output is correct
14 Correct 1126 ms 211916 KB Output is correct
15 Correct 1096 ms 212072 KB Output is correct
16 Correct 1569 ms 212212 KB Output is correct
17 Correct 1389 ms 213392 KB Output is correct
18 Correct 1608 ms 212492 KB Output is correct
19 Correct 1507 ms 212380 KB Output is correct
20 Correct 1648 ms 213352 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 211592 KB Output is correct
2 Correct 788 ms 212188 KB Output is correct
3 Correct 902 ms 212140 KB Output is correct
4 Correct 289 ms 211684 KB Output is correct
5 Correct 570 ms 211868 KB Output is correct
6 Correct 865 ms 211856 KB Output is correct
7 Correct 262 ms 211844 KB Output is correct
8 Correct 645 ms 211808 KB Output is correct
9 Correct 915 ms 212496 KB Output is correct
10 Correct 912 ms 212500 KB Output is correct
11 Correct 927 ms 212492 KB Output is correct
12 Correct 1631 ms 213192 KB Output is correct
13 Correct 1651 ms 213280 KB Output is correct
14 Correct 1126 ms 211916 KB Output is correct
15 Correct 1096 ms 212072 KB Output is correct
16 Correct 1569 ms 212212 KB Output is correct
17 Correct 1389 ms 213392 KB Output is correct
18 Correct 1608 ms 212492 KB Output is correct
19 Correct 1507 ms 212380 KB Output is correct
20 Correct 1648 ms 213352 KB Output is correct
21 Execution timed out 4056 ms 213096 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 211592 KB Output is correct
2 Correct 788 ms 212188 KB Output is correct
3 Correct 902 ms 212140 KB Output is correct
4 Correct 289 ms 211684 KB Output is correct
5 Correct 570 ms 211868 KB Output is correct
6 Correct 865 ms 211856 KB Output is correct
7 Correct 262 ms 211844 KB Output is correct
8 Correct 645 ms 211808 KB Output is correct
9 Correct 915 ms 212496 KB Output is correct
10 Correct 912 ms 212500 KB Output is correct
11 Execution timed out 4069 ms 212984 KB Time limit exceeded
12 Halted 0 ms 0 KB -