Submission #350966

#	Time	Username	Problem	Language	Result	Execution time	Memory
350966		talant117408	Parachute rings (IOI12_rings)	C++17	37 / 100	1278 ms	114400 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, 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 fing_cycles = 0, saiz = 0;
    for(int i = 0; i < n; i++){
        if(!used[i]){
            cycles = 0;
            cnt = 0;
            spcycle = 0;
            to_be.clear();
            st.clear();
            dfs(i);
            if(cycles == 1){
                dfs2(i);
                for(auto to : to_be) special[to] = 1;
                if(cnt == spcycle){
                    fing_cycles++;
                    saiz = spcycle;
                }
            }
        }
    }
    
    int initial = 0;
    for(int i = 0; i < n; i++){
        if(sz(graph[i]) > 2) initial++;
    }
    int ans = 0;
    if(fing_cycles == 0){
      //  cout << initial << endl;
        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++;
                //cout << i << ' ' << sz(graph[i]) << endl;
               // for(auto to : graph[i]){
                   // cout << to << ' ' << sz(graph[to]) << endl;
                //}
                //cout << 'a' << endl;
            }
        }
       // cout << "NO FUCKING CYCLES" << endl;
    }
    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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31