Submission #516198

#	Time	Username	Problem	Language	Result	Execution time	Memory
516198		mosiashvililuka	Newspapers (CEOI21_newspapers)	C++14	100 / 100	68 ms	6848 KiB

newspapers

#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],l[5009],li,bo[5009],P[5009],PI;
int CH[1009][1009];
vector <int> v[1009];
void print(){
	pi=PI;
	for(i=1; i<=PI; i++){
		p[i]=P[i];
	}
	cout<<"YES\n";
	cout<<pi<<"\n";
	for(i=1; i<=pi; i++){
		cout<<p[i]<<" ";
	}
	/*
	cout<<"\n";
	for(i=1; i<=a; i++) CH[0][i]=1;
	for(j=1; j<=pi; j++){
		for(i=1; i<=a; i++){
			CH[j][i]=0;
			for(vector <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
				if(p[j]!=(*it)&&CH[j-1][(*it)]==1){
					CH[j][i]=1;break;
				}
			}
		}
	}
	e=0;
	for(i=1; i<=a; i++){
		if(CH[pi][i]==1) e++;
	}
	cout<<"WRONG: "<<e;
	*/
	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){
	int I=i;
	li++;l[li]=q;bo[q]=1;
	if(DP[q]-kl[q][w]==0){
		pi=0;
		for(j=1; j<=li; j++){
			pi++;p[pi]=l[j];
			for(vector <int>::iterator it=v[l[j]].begin(); it!=v[l[j]].end(); it++){
				if(bo[(*it)]==1) continue;
				if(v[(*it)].size()!=1){
					pi++;p[pi]=(*it);
					pi++;p[pi]=l[j];
				}
			}
		}
		for(i=pi; i>=1; i--){
			pi++;p[pi]=p[i];
		}
		if(PI>pi){
			PI=pi;
			for(i=1; i<=pi; i++) P[i]=p[i];
		}
		i=I;
		//print();
	}
	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);
	}
	li--;bo[q]=0;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;PI=10*a+10;
	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);
	}
	if(PI!=10*a+10){
		print();
	}
	cout<<"NO";
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 8 / 8
• Subtask 3: 80 / 80