oj.uz

Submission #483199

# Submission time Handle Problem Language Result Execution time Memory
483199 2021-10-28T06:58:28 Z abc864197532 Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 98484 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 n, dsu[N], cnt;
bool vis[N], cyc;

void dfs(int v, int pa) {
    vis[v] = true;
    cnt++;
    for (int u : adj[v]) if (u != pa) {
        if (!vis[u])
            dfs(u, v);
        else {
            cyc = true;
        }
    }
}

int Find(int x) {
    if (dsu[x] == x)
        return x;
    return dsu[x] = Find(dsu[x]);
}

void Init(int N) {
    n = N;
}

void Link(int a, int b) {
    adj[a].pb(b), adj[b].pb(a);
    edge.eb(a, b);
}

int check(int x) {
    iota(dsu, dsu + n, 0);
    vector <int> deg(n, 0);
    for (pii e : edge) if (e.X != x && e.Y != x) {
        if (Find(e.X) == Find(e.Y))
            return false;
        dsu[Find(e.X)] = Find(e.Y);
        deg[e.X]++, deg[e.Y]++;
    }
    for (int i = 0; i < n; ++i) if (deg[i] > 2)
        return false;
    return true;
}

int CountCritical() {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        vis[i] = false;
        if (adj[i].size() > 3)
            return check(i);
        if (adj[i].size() == 3) {
            for (int j : adj[i])
                ans += check(j);
            ans += check(i);
            return ans;
        }
    }
    int now = -1;
    for (int i = 0; i < n; ++i) if (!vis[i]) {
        cnt = 0, cyc = false;
        dfs(i, -1);
        if (cyc) {
            if (now != -1)
                return 0;
            now = cnt;
        }
    }
    return now == -1 ? n : now;
}

/*
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 14 ms 23756 KB Output is correct
2 Correct 12 ms 23992 KB Output is correct
3 Correct 12 ms 24080 KB Output is correct
4 Correct 11 ms 23784 KB Output is correct
5 Correct 13 ms 24012 KB Output is correct
6 Correct 13 ms 24260 KB Output is correct
7 Correct 14 ms 23884 KB Output is correct
8 Correct 12 ms 23960 KB Output is correct
9 Correct 13 ms 24028 KB Output is correct
10 Correct 13 ms 24012 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 44588 KB Output is correct
2 Correct 584 ms 61888 KB Output is correct
3 Correct 741 ms 78960 KB Output is correct
4 Correct 912 ms 77772 KB Output is correct
5 Correct 899 ms 78108 KB Output is correct
6 Correct 882 ms 98484 KB Output is correct
7 Correct 634 ms 77488 KB Output is correct
8 Correct 795 ms 80300 KB Output is correct
9 Correct 837 ms 84400 KB Output is correct
10 Correct 493 ms 77004 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 12 ms 23992 KB Output is correct
3 Correct 12 ms 24080 KB Output is correct
4 Correct 11 ms 23784 KB Output is correct
5 Correct 13 ms 24012 KB Output is correct
6 Correct 13 ms 24260 KB Output is correct
7 Correct 14 ms 23884 KB Output is correct
8 Correct 12 ms 23960 KB Output is correct
9 Correct 13 ms 24028 KB Output is correct
10 Correct 13 ms 24012 KB Output is correct
11 Correct 23 ms 24072 KB Output is correct
12 Correct 32 ms 24388 KB Output is correct
13 Correct 39 ms 24424 KB Output is correct
14 Correct 20 ms 24136 KB Output is correct
15 Correct 21 ms 24228 KB Output is correct
16 Correct 31 ms 24312 KB Output is correct
17 Correct 18 ms 24396 KB Output is correct
18 Correct 44 ms 24576 KB Output is correct
19 Correct 30 ms 24308 KB Output is correct
20 Correct 38 ms 24412 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 12 ms 23992 KB Output is correct
3 Correct 12 ms 24080 KB Output is correct
4 Correct 11 ms 23784 KB Output is correct
5 Correct 13 ms 24012 KB Output is correct
6 Correct 13 ms 24260 KB Output is correct
7 Correct 14 ms 23884 KB Output is correct
8 Correct 12 ms 23960 KB Output is correct
9 Correct 13 ms 24028 KB Output is correct
10 Correct 13 ms 24012 KB Output is correct
11 Correct 23 ms 24072 KB Output is correct
12 Correct 32 ms 24388 KB Output is correct
13 Correct 39 ms 24424 KB Output is correct
14 Correct 20 ms 24136 KB Output is correct
15 Correct 21 ms 24228 KB Output is correct
16 Correct 31 ms 24312 KB Output is correct
17 Correct 18 ms 24396 KB Output is correct
18 Correct 44 ms 24576 KB Output is correct
19 Correct 30 ms 24308 KB Output is correct
20 Correct 38 ms 24412 KB Output is correct
21 Execution timed out 4038 ms 24700 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 12 ms 23992 KB Output is correct
3 Correct 12 ms 24080 KB Output is correct
4 Correct 11 ms 23784 KB Output is correct
5 Correct 13 ms 24012 KB Output is correct
6 Correct 13 ms 24260 KB Output is correct
7 Correct 14 ms 23884 KB Output is correct
8 Correct 12 ms 23960 KB Output is correct
9 Correct 13 ms 24028 KB Output is correct
10 Correct 13 ms 24012 KB Output is correct
11 Correct 387 ms 44588 KB Output is correct
12 Correct 584 ms 61888 KB Output is correct
13 Correct 741 ms 78960 KB Output is correct
14 Correct 912 ms 77772 KB Output is correct
15 Correct 899 ms 78108 KB Output is correct
16 Correct 882 ms 98484 KB Output is correct
17 Correct 634 ms 77488 KB Output is correct
18 Correct 795 ms 80300 KB Output is correct
19 Correct 837 ms 84400 KB Output is correct
20 Correct 493 ms 77004 KB Output is correct
21 Correct 23 ms 24072 KB Output is correct
22 Correct 32 ms 24388 KB Output is correct
23 Correct 39 ms 24424 KB Output is correct
24 Correct 20 ms 24136 KB Output is correct
25 Correct 21 ms 24228 KB Output is correct
26 Correct 31 ms 24312 KB Output is correct
27 Correct 18 ms 24396 KB Output is correct
28 Correct 44 ms 24576 KB Output is correct
29 Correct 30 ms 24308 KB Output is correct
30 Correct 38 ms 24412 KB Output is correct
31 Execution timed out 4038 ms 24700 KB Time limit exceeded
32 Halted 0 ms 0 KB -