oj.uz

Submission #350943

# Submission time Handle Problem Language Result Execution time Memory
350943 2021-01-19T10:05:49 Z talant117408 Parachute rings (IOI12_rings) C++17
37 / 100
 1315 ms 114440 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, fcking_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){
                    fcking_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(fcking_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(fcking_cycles > 1) return 0;
        if(fcking_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 3 ms 748 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 35500 KB Output is correct
2 Correct 999 ms 54820 KB Output is correct
3 Correct 1205 ms 82992 KB Output is correct
4 Correct 1239 ms 68564 KB Output is correct
5 Correct 1181 ms 69992 KB Output is correct
6 Correct 1315 ms 114440 KB Output is correct
7 Correct 1132 ms 80496 KB Output is correct
8 Correct 1132 ms 63852 KB Output is correct
9 Correct 1224 ms 69192 KB Output is correct
10 Correct 1160 ms 74040 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 3 ms 748 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Incorrect 10 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 3 ms 748 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Incorrect 10 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 3 ms 748 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 586 ms 35500 KB Output is correct
12 Correct 999 ms 54820 KB Output is correct
13 Correct 1205 ms 82992 KB Output is correct
14 Correct 1239 ms 68564 KB Output is correct
15 Correct 1181 ms 69992 KB Output is correct
16 Correct 1315 ms 114440 KB Output is correct
17 Correct 1132 ms 80496 KB Output is correct
18 Correct 1132 ms 63852 KB Output is correct
19 Correct 1224 ms 69192 KB Output is correct
20 Correct 1160 ms 74040 KB Output is correct
21 Incorrect 10 ms 748 KB Output isn't correct
22 Halted 0 ms 0 KB -