Submission #835581

#	Time	Username	Problem	Language	Result	Execution time	Memory
835581		YassirSalama	Parachute rings (IOI12_rings)	C++17	Compilation error	0 ms	0 KiB

rings

#include "rings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define F first
#define S second
#define pb push_back
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
vector<set<int>> v;
vector<set<int>> cp;
vector<bool> visited;
vector<int> chain;
vector<int> degree;
int n;
void dfs(int node){
	chain.push_back(node);
	degree[node]=cp[node].size();
	visited[node]=true;
	for(auto x:cp[node]){
		if(!visited[x]){
			dfs(x);
		}
	}
}
bool checkchain(int node){
	//so exactly two nodes got degree of 1
	//and chainlength-2 nodes got degee of 2
	chain.clear();
	dfs(node);
	int unifreq=0;
	int doublefreq=0;
	// dbg(node);
	// OVL(chain," ")
	if(chain.size()==1) return true;
	for(auto x:chain){
		// dbg(x,degree[x]);
		if(degree[x]==1) unifreq++;
		else if(degree[x]==2) doublefreq++;
		else return false;
	}
	return (unifreq==2&&chain.size()-2==doublefreq)||chain.size()==1;

}
void Init(int N){
	n=N;
	visited.resize(N,false);
	v.resize(N+1);
	for(auto x:v) x.clear();
	degree.resize(N+1,0);
}
void Link(int A, int B){
	// cout<<"Link"<<A<<" "<<B<<endl;
	v[A].insert(B);
	v[B].insert(A);
}
int CountCritical(){
	int ans=0;
	for(int i=0;i<n;i++){
		cp=v;
		for(auto x:v[i]){
			cp[i].erase(x);
			cp[x].erase(i);
		}
		degree.assign(n,0);
		visited.assign(n,false);
		bool ok=true;
		for(int j=0;j<n;j++){
			if(!visited[j]&&j!=n){
				bool x;
				x=checkchain(j);
				// dbg(j,x);
				ok&=x;
			}
		}
		ans+=ok;
	}
	return ans;
}

#ifdef IOI
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m;
cin>>n>>m;
Init(n);
for(int i=0;i<m;i++){
	int k;
	cin>>k;
	if(k!=-1){
		int a=k;
		int b;
		cin>>b;
		Link(a,b);
	}else{
		cout<<"! "<<CountCritical()<<endl;
	}
}
}
#endif

Compilation message (stderr)

rings.cpp:1:10: fatal error: rings.h: No such file or directory
    1 | #include "rings.h"
      |          ^~~~~~~~~
compilation terminated.