제출 #1142971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142971		aguss	낙하산 고리들 (IOI12_rings)	C++20	20 / 100	4094 ms	118764 KiB

rings

#include<bits/stdc++.h>
using namespace std;

int n, q;
vector<unordered_set<int>> graph;
vector<bool> vis;
void Init(int N_) {

  	n = N_;
	graph.assign(n, unordered_set<int>(0));

}

void Link(int a, int b) {
	graph[a].insert(b);
	graph[b].insert(a);
}
bool dfs(int node, int parent, int toerase){
    for(auto x : graph[node]){
        if(x == toerase){
            continue;
        }
        if(graph[x].size() - graph[x].count(toerase) > 2){ 
            return 0;
        }
        if(vis[x]){
            if(x == parent){
                continue;
            }
            return 0;
        }
        vis[x] = 1;
        bool ans = dfs(x, node, toerase);
        if(!ans){
            return 0;
        }
    }
    return 1;
}
int CountCritical() {
	vis.assign(n, 0);
    int ans = 0;
    for(int i = 0; i < n; i++){
        bool t = 1;
        for(int j = 0; j < n; j++){
            if(j == i){
                continue;
            } 
            if(!vis[j]){
                vis[j] = 1;
                if(!dfs(j, -1, i)){
                    t = 0;
                	  break;
                }
            }
        }
        if(t){
            ans++;
        }
        vis.assign(n, 0);
 
    }
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31