oj.uz

Submission #350946

# Submission time Handle Problem Language Result Execution time Memory
350946 2021-01-19T10:06:28 Z talant117408 Parachute rings (IOI12_rings) C++17
37 / 100
 1314 ms 114288 KB 
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

vector <vector <int>> graph;
bool in_cycle[1000007];
int n, cycles, cnt, used[1000007], used2[1000007], spcycle;
vector <int> st, to_be;

void dfs(int v, int p = -1){
    st.pb(v);
    used[v] = 1;
    for(auto to : graph[v]){
        if(p == to) continue;
        if(used[to] == 1){
            int flag = 0;
            if(!cycles){
                for(auto to2 : st){
                    if(to2 == to) flag = 1;
                    if(flag) in_cycle[to2] = 1;
                }
            }
            cycles++;
        }
        else if(!used[to]){
            dfs(to, v);
        }
    }
    used[v] = 2;
    st.pop_back();
}

void dfs2(int v, int p = -1){
    used2[v] = 1;
    cnt++;
    if(in_cycle[v]) spcycle++;
    for(auto to : graph[v]){
        if(in_cycle[v] && !in_cycle[to]){
            to_be.pb(to);
        }
        if(p == to) continue;
        if(!used2[to]) dfs2(to, v);
    }
}

void Init(int N) {
    n = N;
    graph.resize(n+1);
}

void Link(int A, int B) {
    graph[A].pb(B);
    graph[B].pb(A);
}

int CountCritical(){
    int special[n];
    for(int i = 0; i < n; i++){
        used[i] = 0;
        special[i] = 0;
        used2[i] = 0;
        in_cycle[i] = 0;
    }
    int com = 0, fing_cycles = 0, saiz = 0;
    for(int i = 0; i < n; i++){
        if(!used[i]){
            com++;
            cycles = cnt = spcycle = 0;
            dfs(i);
            if(cycles == 1){
                dfs2(i);
                for(auto to : to_be) special[to] = 1;
                to_be.clear();
                if(cnt == spcycle){
                    fing_cycles++;
                    saiz = spcycle;
                }
            }
            st.clear();
        }
    }
    
    int initial = 0;
    for(int i = 0; i < n; i++){
        if(sz(graph[i]) > 2) initial++;
    }
    int ans = 0;
    if(fing_cycles == 0){
        for(int i = 0; i < n; i++){
            if(special[i]) continue;
            int tmp = initial - (sz(graph[i]) > 2 ? 1 : 0);
            for(auto to : graph[i]){
                if(sz(graph[to]) == 3) tmp--;
            }
            if(!tmp){
                ans++;
            }
        }
    }
    else if(initial == 0){
        if(fing_cycles > 1) return 0;
        if(fing_cycles == 1) return saiz;
        return n;
    }
    return ans;
}
/*
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 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 35544 KB Output is correct
2 Correct 1153 ms 54736 KB Output is correct
3 Correct 1180 ms 82920 KB Output is correct
4 Correct 1137 ms 68716 KB Output is correct
5 Correct 1159 ms 69816 KB Output is correct
6 Correct 1314 ms 114288 KB Output is correct
7 Correct 1108 ms 80612 KB Output is correct
8 Correct 1151 ms 64072 KB Output is correct
9 Correct 1246 ms 69128 KB Output is correct
10 Correct 1114 ms 74012 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Incorrect 11 ms 748 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Incorrect 11 ms 748 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 546 ms 35544 KB Output is correct
12 Correct 1153 ms 54736 KB Output is correct
13 Correct 1180 ms 82920 KB Output is correct
14 Correct 1137 ms 68716 KB Output is correct
15 Correct 1159 ms 69816 KB Output is correct
16 Correct 1314 ms 114288 KB Output is correct
17 Correct 1108 ms 80612 KB Output is correct
18 Correct 1151 ms 64072 KB Output is correct
19 Correct 1246 ms 69128 KB Output is correct
20 Correct 1114 ms 74012 KB Output is correct
21 Incorrect 11 ms 748 KB Output isn't correct
22 Halted 0 ms 0 KB -