제출 #350861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
350861		talant117408	낙하산 고리들 (IOI12_rings)	C++17	0 / 100	4018 ms	72052 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;

int n;
vector <vector <int>> graph;
int timer, special[1000007], cycles, tin[1000007];
int used[1000007];
vector <int> to_be;
set <pii> st;

void dfs(int v, int p = -1){
    tin[v] = ++timer;
    st.insert(mp(tin[v], v));
    used[v] = 1;
    for(auto to : graph[v]){
        if(p == to) continue;
        if(used[to] == 1){
            cycles++;
            auto it = (st.lb(mp(tin[to], to)));
            map <int, bool> t;
            for(auto iter = it; iter != st.end(); iter++){
                t[(*iter).second] = 1;
            }
            vector <int> ss;
            for(auto iter = it; iter != st.end(); iter++){
                for(auto to2 : graph[(*iter).second]){
                    if(!t.count(to2)){
                        ss.pb(to2);
                    }
                }
            }
            if(sz(ss) == 1)
                to_be.pb(ss[0]);
        }
        else if(!used[to]){
            dfs(to, v);
        }
    }
    used[v] = 2;
    st.erase(st.find(mp(tin[v], 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(){
    /*timer = cnt = 0;
    for(int i = 0; i < n; i++){
        used[i] = 0;
        tin[i] = fup[i] = 0;
    }
    
    vector <int> comps;
    for(int i = 0; i < n; i++){
        if(!used[i]){
            dfs(i);
            comps.pb(in_cmp);
            in_cmp = 0;
        }
    }
    
    if(sz(comps) > 2){
        return n;
    }
    else if(sz(comps) == 2){
        return (comps[0] > 1 ? comps[0] : 0)+(comps[1] > 1 ? comps[1] : 0);
    }*/
    
    for(int i = 0; i < n; i++){
        used[i] = 0;
        special[i] = 0;
        tin[i] = 0;
    }
    
    for(int i = 0; i < n; i++){
        if(!used[i]){
            cycles = timer = 0;
            dfs(i);
            if(cycles == 1 && sz(to_be) == 1){
                special[to_be.back()]++;
            }
            to_be.clear();
            st.clear();
        }
    }
    
    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