oj.uz

Submission #425225

# Submission time Handle Problem Language Result Execution time Memory
425225 2021-06-12T16:19:53 Z wiwiho Parachute rings (IOI12_rings) C++14
55 / 100
 4000 ms 108916 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define printv(a, b) {\
    for(auto pv : a) b << pv << " ";\
    b << "\n";\
}

using namespace std;

int n;

vector<vector<int>> g;
vector<int> in, low;
vector<int> pr;

void Init(int N){
    n = N;
    g.resize(n);
}

void Link(int u, int v){
    g[u].eb(v);
    g[v].eb(u);
}

int ts = 0;

void dfs(int now, int p){
    in[now] = ts++;
    low[now] = in[now];
    pr[now] = p;
    for(int i : g[now]){
        if(in[i] != -1){
            low[now] = min(low[now], in[i]);
            continue;
        }
        dfs(i, now);
        low[now] = min(low[now], low[i]);
    }
}

int CountCritical(){
    ts = 0;
    in.clear();
    low.clear();
    pr.clear();
    in.resize(n, -1);
    low.resize(n);
    pr.resize(n);

    int con = 0;
    for(int i = 0; i < n; i++){
        if(in[i] != -1) continue;
        con++;
        dfs(i, i);
    }

    int zero = 0, one = 0, two = 0, more = 0;
    for(int i = 0; i < n; i++){
        int deg = g[i].size();
        if(deg == 0) zero++;
        else if(deg == 1) one++;
        else if(deg == 2) two++;
        else more++;
    }
  
    int ans = 0;   
    /*cerr << "query " << one << " " << two << " " << more << " " << con << "\n";
    printv(in, cerr);
    printv(low, cerr);
    printv(pr, cerr);*/

    for(int i = 0; i < n; i++){
        int deg = g[i].size();
        if(deg == 0) zero--;
        else if(deg == 1) one--;
        else if(deg == 2) two--;
        else more--;
        for(int j : g[i]){
            int d = g[j].size();
            if(d == 0) zero--;
            else if(d == 1) one--;
            else if(d == 2) two--;
            else more--;
            if(d - 1 == 0) zero++;
            else if(d - 1 == 1) one++;
            else if(d - 1 == 2) two++;
            else more++;
            if(pr[j] == i && low[j] >= in[i]) con++;
        }
        if(pr[i] == i) con--;
        
        //cerr << "test " << i << "\n";
        //cerr << one << " " << two << " " << more << " " << con << "\n";
        if(more == 0 && one == (con - zero) * 2) ans++;

        if(deg == 0) zero++;
        else if(deg == 1) one++;
        else if(deg == 2) two++;
        else more++;
        for(int j : g[i]){
            int d = g[j].size();
            if(d == 0) zero++;
            else if(d == 1) one++;
            else if(d == 2) two++;
            else more++;
            if(d - 1 == 0) zero--;
            else if(d - 1 == 1) one--;
            else if(d - 1 == 2) two--;
            else more--;
            if(pr[j] == i && low[j] >= in[i]) con--;
        }
        if(pr[i] == i) con++;
    }

    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 41924 KB Output is correct
2 Correct 1205 ms 64588 KB Output is correct
3 Correct 1408 ms 90088 KB Output is correct
4 Correct 1593 ms 80780 KB Output is correct
5 Correct 1561 ms 81628 KB Output is correct
6 Correct 1537 ms 108916 KB Output is correct
7 Correct 1353 ms 87372 KB Output is correct
8 Correct 1420 ms 75312 KB Output is correct
9 Correct 1489 ms 81192 KB Output is correct
10 Correct 1150 ms 82728 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 17 ms 716 KB Output is correct
12 Correct 80 ms 1460 KB Output is correct
13 Correct 74 ms 1420 KB Output is correct
14 Correct 51 ms 908 KB Output is correct
15 Correct 69 ms 1236 KB Output is correct
16 Correct 60 ms 1024 KB Output is correct
17 Correct 63 ms 1084 KB Output is correct
18 Correct 123 ms 1520 KB Output is correct
19 Correct 74 ms 1024 KB Output is correct
20 Correct 78 ms 1060 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 17 ms 716 KB Output is correct
12 Correct 80 ms 1460 KB Output is correct
13 Correct 74 ms 1420 KB Output is correct
14 Correct 51 ms 908 KB Output is correct
15 Correct 69 ms 1236 KB Output is correct
16 Correct 60 ms 1024 KB Output is correct
17 Correct 63 ms 1084 KB Output is correct
18 Correct 123 ms 1520 KB Output is correct
19 Correct 74 ms 1024 KB Output is correct
20 Correct 78 ms 1060 KB Output is correct
21 Execution timed out 4019 ms 2704 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 636 ms 41924 KB Output is correct
12 Correct 1205 ms 64588 KB Output is correct
13 Correct 1408 ms 90088 KB Output is correct
14 Correct 1593 ms 80780 KB Output is correct
15 Correct 1561 ms 81628 KB Output is correct
16 Correct 1537 ms 108916 KB Output is correct
17 Correct 1353 ms 87372 KB Output is correct
18 Correct 1420 ms 75312 KB Output is correct
19 Correct 1489 ms 81192 KB Output is correct
20 Correct 1150 ms 82728 KB Output is correct
21 Correct 17 ms 716 KB Output is correct
22 Correct 80 ms 1460 KB Output is correct
23 Correct 74 ms 1420 KB Output is correct
24 Correct 51 ms 908 KB Output is correct
25 Correct 69 ms 1236 KB Output is correct
26 Correct 60 ms 1024 KB Output is correct
27 Correct 63 ms 1084 KB Output is correct
28 Correct 123 ms 1520 KB Output is correct
29 Correct 74 ms 1024 KB Output is correct
30 Correct 78 ms 1060 KB Output is correct
31 Execution timed out 4019 ms 2704 KB Time limit exceeded
32 Halted 0 ms 0 KB -