Submission #576812

#	Time	Username	Problem	Language	Result	Execution time	Memory
576812		juggernaut	Newspapers (CEOI21_newspapers)	C++14	9 / 100	2 ms	1236 KiB

newspapers

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int a[20];
int n,m;
bool dp[1<<20];
pair<int,int>path[1<<20];
void go(int mask){
	dp[mask]=true;
	for(int i=0;i<n;i++)if(mask>>i&1){
		int new_mask=0;
		for(int j=0;j<n;j++)if((mask>>j&1)&&(i^j))new_mask|=a[j];
		if(dp[new_mask])continue;
		path[new_mask]=make_pair(mask,i);
		go(new_mask);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		x--;y--;
		a[x]|=(1<<y);
		a[y]|=(1<<x);
	}
	int mx=(1<<n)-1;
	go(mx);
	if(dp[0]){
		int cur_mask=0;
		vector<int>vec;
		while(cur_mask!=mx){
			vec.push_back(path[cur_mask].sc+1);
			cur_mask=path[cur_mask].fr;
		}
		reverse(vec.begin(),vec.end());
		puts("YES");
		printf("%d\n",(int)vec.size());
		for(int to:vec)printf("%d ",to);
	}else puts("NO");
}

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
newspapers.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

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