oj.uz

Submission #516168

# Submission time Handle Problem Language Result Execution time Memory
516168 2022-01-20T14:30:37 Z mosiashvililuka Newspapers (CEOI21_newspapers) C++14
0 / 100
 1 ms 344 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,p[5009],pi,kl[1003][1003],DP[1009];
vector <int> v[1009];
void print(){
	cout<<"YES\n";
	cout<<pi<<"\n";
	for(i=1; i<=pi; i++){
		cout<<p[i]<<" ";
	}
	exit(0);
}
void dfs(int q, int w, int rr){
	e=max(e,rr);
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q,rr+1);
	}
}
void dfs2(int q, int w){
	if(DP[q]-kl[q][w]==0){
		cout<<"YES";
		exit(0);
	}
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		if(DP[q]-kl[q][w]-kl[q][(*it)]!=0) continue;
		dfs2((*it),q);
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=b; i++){
		cin>>c>>d;
		v[c].push_back(d);
		v[d].push_back(c);
	}
	if(a==1){
		pi=1;p[1]=1;
		print();
	}
	if(a==2){
		pi=2;p[1]=1;p[2]=1;
		print();
	}
	if(b!=a-1){
		cout<<"NO";
		return 0;
	}
	for(i=1; i<=a; i++){
		for(vector <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
			e=0;
			dfs((*it),i,1);
			if(e>2){
				kl[i][(*it)]=1;DP[i]++;
			}
		}
	}
	for(i=1; i<=a; i++){
		dfs2(i,0);
	}
	cout<<"NO";
	return 0;
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 1 ms 344 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 0 ms 332 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 1 ms 344 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -