Submission #350886

#	Time	Username	Problem	Language	Result	Execution time	Memory
350886		talant117408	Parachute rings (IOI12_rings)	C++17	0 / 100	1267 ms	83028 KiB

rings

#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, used[1000007], used2[1000007];
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;
    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);
}

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;
    }
    
    for(int i = 0; i < n; i++){
        if(!used[i]){
            cycles = 0;
            dfs(i);
            if(cycles == 1){
                dfs2(i);
                if(sz(to_be) == 1){
                    special[to_be.back()] = 1;
                }
            }
        }
    }
    
    int initial = 0;
    for(int i = 0; i < n; i++){
        if(sz(graph[i]) > 2) initial++;
    }
    int ans = 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++;
        }
    }
    
    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: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31