Submission #592091

#	Time	Username	Problem	Language	Result	Execution time	Memory
592091		SeDunion	Newspapers (CEOI21_newspapers)	C++17	12 / 100	499 ms	214640 KiB

newspapers

#include <iostream>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;
 
const int N = 2e6 + 66;
 
vector<pair<int,int>>G[N];
pair<int,int>p[N];
 
int d[N];
 
int ea[N], eb[N];
 
int cnt[N], mp[33][33];
 
int cycle;
vector<int>g[N];
 
int used[N];
 
void dfs(int v, int p = -1) {
	used[v] = 1;
	for (int to : g[v]) if (to != p) {
		if (used[to] == 1) cycle = 1;
		if (used[to] == 0) dfs(to, v);
	}
	used[v] = 2;
}
 
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0 ; i < m ; ++ i) cin >> ea[i] >> eb[i];
	for (int i = 0 ; i < m ; ++ i) ea[i]--, eb[i]--, mp[ea[i]][eb[i]] = mp[eb[i]][ea[i]] = 1, g[ea[i]].emplace_back(eb[i]), g[eb[i]].emplace_back(ea[i]);
	for (int i = 1 ; i <= n ; ++ i) if (!used[i]) {
		dfs(i);
	}
	if (cycle) {
		cout << "NO";
		return 0;
	}
	for (int mask = 1 ; mask < (1 << n) ; ++ mask) {
		for (int i = 0 ; i < n ; ++ i) cnt[i] = 0;
		int nms = 0;
			for (int j = 0 ; j < m ; ++ j) {
				int x = ea[j], y = eb[j];
				if (mask >> y & 1) cnt[x]++, nms |= (1 << x);
				if (mask >> x & 1) cnt[y]++, nms |= (1 << y);
			}
		for (int i = 0 ; i < n ; ++ i) if (mask >> i & 1) {
			int gms = nms;
			for (int j : g[i]) {
				if (cnt[j] == 1) gms ^= (1 << j);
			}
			G[gms].emplace_back(mask, i + 1);
		}
	}
	for (int i = 0 ; i < (1 << n) ; ++ i) d[i] = -1;
	d[0] = 0;
	queue<int>q;
	q.push(0);
	while (q.size()) {
		int v = q.front(); q.pop();
		for (auto [to, w] : G[v]) if (d[to] == -1) {
			p[to] = {v, w};
			d[to] = d[v] + 1;
			q.push(to);
		}
	}
	if (d[(1 << n) - 1] == -1) {
		cout << "NO";
		return 0;
	}
	cout << "YES\n";
	cout << d[(1 << n) - 1] << "\n";
	int x = (1 << n) - 1;
	while (x) {
		cout << p[x].second << " ";
		x = p[x].first;
	}
}

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