Submission #786950

#	Time	Username	Problem	Language	Result	Execution time	Memory
786950		CSQ31	Newspapers (CEOI21_newspapers)	C++17	75 / 100	153 ms	7028 KiB

newspapers

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
bool vis[1111];
int par[1111],depth[1111],n,m;
vector<int>adj[1111];
void dfs1(int v,int u){
	for(int x:adj[v]){
		if(x == u)continue;
		depth[x] = depth[v]+1;
		par[x] = v;
		dfs1(x,v);
	}
}
int search(int s){
	for(int i=1;i<=n;i++)depth[i] = 0;
	dfs1(s,-1);
	int mx = 0;
	int res = 0;
	for(int i=1;i<=n;i++)if(depth[i] > mx){mx=depth[i],res=i;}
	return res;
}
void no(){
	cout<<"NO";
	exit(0);
	
}
bool inpath[1111];
bool check(int v,int u,int dep){
	if(dep>=3)return 1;
	for(int x:adj[v]){
		if(x==u || inpath[x])continue;
		if(check(x,v,dep+1))return 1;
	}
	return 0;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int v,u;
		cin>>v>>u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	if(m>=n)no();
	if(n<=2){
		cout<<"YES"<<'\n';
		cout<<2<<'\n';
		cout<<"1 1";
		return 0;
		
	}
	int s = search(1);
	int t = search(s);
	
	vector<int>path;
	while(true){
		inpath[t] = 1;
		path.pb(t);
		if(t==s)break;
		t = par[t];
	}
	reverse(all(path));
	vector<int>ans;
	for(int i=1;i+1<sz(path);i++){
		int v = path[i];
		ans.pb(v);
		if(check(v,0,0))no();
		for(int x:adj[v]){
			if(inpath[x])continue;
			ans.pb(x);
			ans.pb(v);
		}
	}
	int k = sz(ans);
	for(int i=k-1;i>=0;i--)ans.pb(ans[i]);
	cout<<"YES"<<'\n';
	cout<<sz(ans)<<'\n';
	for(int i=0;i<sz(ans);i++)cout<<ans[i]<<" ";
}

• Subtask 1: 9 / 12
• Subtask 2: 6 / 8
• Subtask 3: 60 / 80