oj.uz

Submission #835586

# Submission time Handle Problem Language Result Execution time Memory
835586 2023-08-23T16:20:30 Z YassirSalama Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 155424 KB 
#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

rings.cpp: In function 'bool checkchain(int)':
rings.cpp:44:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |  return (unifreq==2&&chain.size()-2==doublefreq)||chain.size()==1;
      |                      ~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1150 ms 1552 KB Output is correct
3 Correct 1721 ms 1848 KB Output is correct
4 Correct 42 ms 584 KB Output is correct
5 Correct 541 ms 1272 KB Output is correct
6 Correct 1904 ms 2004 KB Output is correct
7 Correct 483 ms 912 KB Output is correct
8 Correct 1066 ms 1524 KB Output is correct
9 Correct 1767 ms 1892 KB Output is correct
10 Correct 1792 ms 1824 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 155424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1150 ms 1552 KB Output is correct
3 Correct 1721 ms 1848 KB Output is correct
4 Correct 42 ms 584 KB Output is correct
5 Correct 541 ms 1272 KB Output is correct
6 Correct 1904 ms 2004 KB Output is correct
7 Correct 483 ms 912 KB Output is correct
8 Correct 1066 ms 1524 KB Output is correct
9 Correct 1767 ms 1892 KB Output is correct
10 Correct 1792 ms 1824 KB Output is correct
11 Execution timed out 4033 ms 1028 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1150 ms 1552 KB Output is correct
3 Correct 1721 ms 1848 KB Output is correct
4 Correct 42 ms 584 KB Output is correct
5 Correct 541 ms 1272 KB Output is correct
6 Correct 1904 ms 2004 KB Output is correct
7 Correct 483 ms 912 KB Output is correct
8 Correct 1066 ms 1524 KB Output is correct
9 Correct 1767 ms 1892 KB Output is correct
10 Correct 1792 ms 1824 KB Output is correct
11 Execution timed out 4033 ms 1028 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1150 ms 1552 KB Output is correct
3 Correct 1721 ms 1848 KB Output is correct
4 Correct 42 ms 584 KB Output is correct
5 Correct 541 ms 1272 KB Output is correct
6 Correct 1904 ms 2004 KB Output is correct
7 Correct 483 ms 912 KB Output is correct
8 Correct 1066 ms 1524 KB Output is correct
9 Correct 1767 ms 1892 KB Output is correct
10 Correct 1792 ms 1824 KB Output is correct
11 Execution timed out 4083 ms 155424 KB Time limit exceeded
12 Halted 0 ms 0 KB -