Submission #772302

#	Time	Username	Problem	Language	Result	Execution time	Memory
772302		tolbi	Newspapers (CEOI21_newspapers)	C++17	100 / 100	69 ms	20052 KiB

newspapers

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz!..
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, size_t Y> istream& operator>>(istream& is, array<X,Y> arr){for (auto &it : arr) is>>it; return is;}
template<typename T> istream& operator>>(istream& is, vector<T> arr){for (auto &it : arr) is>>it; return is;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define endl '\n'
#define int long long
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vint(x) vector<int> x
#define cinarr(x) for(auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
const int ahmet23 = ((23-2)&23&3);
vector<vector<int>> arr;
int32_t main(){
	ios;
	int T = 1;
	if (!T) cin>>T;
	int tno = 0;
	while (T-(tno++)){
		deci(n);deci(m);
		vector<pair<int,int>> ed;
		arr.resize(n);
		for (int i = 0; i < m; ++i)
		{
			deci(u);deci(v);
			ed.push_back({u,v});
			arr[u-1].push_back(v-1);
			arr[v-1].push_back(u-1);
		}
		if (m!=n-1){
			cout<<"NO"<<endl;
			continue;
		}
		if (n==1){
			cout<<"YES"<<endl;
			cout<<1<<endl<<1<<endl;
			continue;
		}
		if (n==2){
			cout<<"YES"<<endl;
			cout<<2<<endl<<1<<" "<<1<<endl;
			continue;
		}
		queue<int> q;
		q.push(0);
		vector<int> par(n,-1);
		vector<int> dp(n,0);
		while (q.size()){
			int node = q.front();
			q.pop();
			if (par[node]==-1) dp[node]=0;
			else dp[node]=dp[par[node]]+1;
			for (int i = 0; i < arr[node].size(); i++){
				if (par[node]==arr[node][i]) continue;
				par[arr[node][i]]=node;
				q.push(arr[node][i]);
			}
		}
		int nn = 0;
		for (int i = 0; i < n; i++){
			if (dp[i]>dp[nn]) nn = i;
		}
		q.push(nn);
		int a = nn;
		fill(par.begin(), par.end(), -1);
		fill(dp.begin(), dp.end(), -1);
		while (q.size()){
			int node = q.front();
			q.pop();
			if (par[node]==-1) dp[node]=0;
			else dp[node]=dp[par[node]]+1;
			for (int i = 0; i < arr[node].size(); i++){
				if (par[node]==arr[node][i]) continue;
				par[arr[node][i]]=node;
				q.push(arr[node][i]);
			}
		}
		nn = 0;
		for (int i = 0; i < n; i++){
			if (dp[i]>dp[nn]) nn = i;
		}
		int b = nn;
		vector<bool> whitelist(n,false);
		vector<int> whit;
		while (b!=a){
			whitelist[b]=true;
			whit.push_back(b);
			b=par[b];
		}
		whit.push_back(a);
		whitelist[a]=true;
		bool boolean=true;
		vector<vector<int>> coc(n);
		for (int i = 0; i < n; ++i)
		{
			int uza = 0;
			int node = i;
			while (!whitelist[node]){
				uza++;
				node=par[node];
			}
			if (uza==2){
				coc[node].push_back(i);
			}
			if (uza>=3){
				boolean=false;
				break;
			}
		}
		if (!boolean){
			cout<<"NO"<<endl;
			continue;
		}
		cout<<"YES"<<endl;
		vector<int> ans;
		whit.pop_back();
		rev(whit);
		whit.pop_back();
		rev(whit);
		for (int aa = 0; aa < whit.size(); ++aa)
		{
			int root = whit[aa];
			ans.push_back(root+1);
			sort(coc[root].begin(), coc[root].end(), [&](int a, int b){
				return par[a]<par[b];
			});
			for (int i = 0; i < coc[root].size(); ++i)
			{
				if (i && par[coc[root][i]]==par[coc[root][i-1]]) continue;
				ans.push_back(par[coc[root][i]]+1);
				ans.push_back(root+1);
			}
		}
		int ss = ans.size();
		for (int i = ss-1; i >= 0; --i)
		{
			ans.push_back(ans[i]);
		}
		cout<<ans.size()<<endl;
		coutarr(ans);
	}
}

Compilation message (stderr)

newspapers.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
newspapers.cpp: In function 'int32_t main()':
newspapers.cpp:71:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
newspapers.cpp:90:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
newspapers.cpp:138:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for (int aa = 0; aa < whit.size(); ++aa)
      |                    ~~~^~~~~~~~~~~~~
newspapers.cpp:145:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    for (int i = 0; i < coc[root].size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~~~~

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