oj.uz

Submission #576814

# Submission time Handle Problem Language Result Execution time Memory
576814 2022-06-13T14:50:18 Z temporary_juggernaut Newspapers (CEOI21_newspapers) C++14
0 / 100
 0 ms 212 KB 
#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];
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;
	queue<int>q;
	q.push(mx);
	dp[mx]=true;
	while(!q.empty()){
		int mask=q.front();
		q.pop();
		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);
			dp[mask]=true;
			q.push(new_mask);
		}
	}
	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

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

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -