oj.uz

Submission #959851

# Submission time Handle Problem Language Result Execution time Memory
959851 2024-04-09T08:34:20 Z mansur Newspapers (CEOI21_newspapers) C++17
8 / 100
 65 ms 27884 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
 
#include<bits/stdc++.h>	
 
using namespace std;
 
#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 2e5 + 1, mod = 1e9 + 7;
 
const ll inf = 2e9;
 
double eps = 1e-15;
                                                
bool flg = 0;
 
vector<int> gr(N), st[1 << 20];
int n, m, was[1 << 20];

vector<int> f(int msk) {
	if (was[msk]) return st[msk];
	if (!msk) return {};
	was[msk] = 1;
	vector<int> ans(101); 
	st[msk] = ans;                  	
	vector<int> s;
	for (int i = 0; i < n; i++) {
		if (msk >> i & 1) {
			s.push_back(i);
		}	
	}
	vector<int> pr(sz(s)), sf(sz(s));
	for (int i = 0; i < sz(s); i++) {
		if (i) pr[i] = pr[i - 1];
		pr[i] |= gr[s[i]];
	}
	for (int i = sz(s) - 1; i >= 0; i--) {
		if (i < sz(s) - 1) sf[i] = sf[i + 1];
		sf[i] |= gr[s[i]];
	}
	for (int i = 0; i < sz(s); i++) {
		int mask = 0;
		if (i) mask |= pr[i - 1];
		if (i < sz(s) - 1) mask |= sf[i + 1];
		vector<int> x = f(mask);
		x.push_back(s[i]);
		if (sz(x) < sz(ans)) ans = x;
	}
	st[msk] = ans;
	return ans;
}
                                        	
void slv() {
	cin >> n >> m;
	if (m > n - 1) {
		cout << "NO";
		return;
	}
	vector<int> g[n];
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if (n <= 7) {
		for (int i = 0; i < n; i++) {
			for (int to: g[i]) {
				gr[i] |= (1 << to);
			}
		}
		vector<int> ans = f((1 << n) - 1);
		if (sz(ans) > 5 * n) cout << "NO\n";
		else {
			reverse(all(ans));
			cout << "YES\n" << sz(ans) << '\n';
			for (int x: ans) cout << x + 1 << ' ';
		}
		return;
	}
	vector<int> s, ans;
	for (int i = 1; i <= n; i++) s.push_back(i);
	for (int i = 1; i <= 10 * n && sz(s); i++) {
		int pos = min(sz(s) - 1, 1);
		ans.push_back(s[pos]);
		vector<bool> is(n + 2);
		for (int j = 0; j < sz(s); j++) {
			if (j == pos) continue;
			is[s[j] - 1] = is[s[j] + 1] = 1;
		}
		s.clear();
		for (int i = 1; i <= n; i++) {
			if (is[i]) s.push_back(i);
		}
	}
	cout << "YES\n";
	cout << (n - 2) * 2 << '\n';
	for (int i = 2; i < n; i++) cout << i << ' ';
	if (n & 1) {
		for (int i = 2; i < n; i++) cout << i << ' ';
	}else {	
		for (int i = n - 1; i >= 2; i--) cout << i << ' ';
	}
}                                                                           
 
main() {
	//freopen("input.txt", "r", stdin);                                                                                     
	//freopen("output.txt", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {  	
		slv();
	}
}
//wenomechainsama

Compilation message

newspapers.cpp:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main() {
      | ^~~~

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27736 KB Output is correct
2 Correct 6 ms 27740 KB Output is correct
3 Correct 6 ms 27740 KB Output is correct
4 Correct 9 ms 27740 KB Output is correct
5 Correct 6 ms 27740 KB Output is correct
6 Correct 6 ms 27740 KB Output is correct
7 Correct 7 ms 27736 KB Output is correct
8 Correct 6 ms 27740 KB Output is correct
9 Incorrect 7 ms 27740 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27640 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 7 ms 27740 KB Output is correct
4 Correct 6 ms 27740 KB Output is correct
5 Correct 7 ms 27740 KB Output is correct
6 Correct 7 ms 27740 KB Output is correct
7 Correct 7 ms 27740 KB Output is correct
8 Correct 7 ms 27740 KB Output is correct
9 Correct 7 ms 27740 KB Output is correct
10 Correct 7 ms 27736 KB Output is correct
11 Correct 53 ms 27740 KB Output is correct
12 Correct 20 ms 27740 KB Output is correct
13 Correct 28 ms 27736 KB Output is correct
14 Correct 29 ms 27816 KB Output is correct
15 Correct 31 ms 27800 KB Output is correct
16 Correct 58 ms 27872 KB Output is correct
17 Correct 58 ms 27740 KB Output is correct
18 Correct 60 ms 27884 KB Output is correct
19 Correct 65 ms 27848 KB Output is correct
20 Correct 57 ms 27736 KB Output is correct

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27736 KB Output is correct
2 Correct 6 ms 27740 KB Output is correct
3 Correct 6 ms 27740 KB Output is correct
4 Correct 9 ms 27740 KB Output is correct
5 Correct 6 ms 27740 KB Output is correct
6 Correct 6 ms 27740 KB Output is correct
7 Correct 7 ms 27736 KB Output is correct
8 Correct 6 ms 27740 KB Output is correct
9 Incorrect 7 ms 27740 KB Output isn't correct
10 Halted 0 ms 0 KB -