oj.uz

Submission #959853

# Submission time Handle Problem Language Result Execution time Memory
959853 2024-04-09T08:34:35 Z mansur Newspapers (CEOI21_newspapers) C++17
8 / 100
 73 ms 27992 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 <= 9) {
		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 11 ms 27740 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 6 ms 27740 KB Output is correct
4 Correct 11 ms 27740 KB Output is correct
5 Correct 9 ms 27740 KB Output is correct
6 Correct 6 ms 27740 KB Output is correct
7 Correct 7 ms 27604 KB Output is correct
8 Correct 7 ms 27740 KB Output is correct
9 Incorrect 8 ms 27992 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 27616 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 8 ms 27736 KB Output is correct
4 Correct 7 ms 27640 KB Output is correct
5 Correct 8 ms 27640 KB Output is correct
6 Correct 6 ms 27740 KB Output is correct
7 Correct 8 ms 27740 KB Output is correct
8 Correct 7 ms 27740 KB Output is correct
9 Correct 7 ms 27748 KB Output is correct
10 Correct 7 ms 27740 KB Output is correct
11 Correct 60 ms 27840 KB Output is correct
12 Correct 25 ms 27740 KB Output is correct
13 Correct 26 ms 27748 KB Output is correct
14 Correct 30 ms 27740 KB Output is correct
15 Correct 31 ms 27740 KB Output is correct
16 Correct 73 ms 27868 KB Output is correct
17 Correct 57 ms 27896 KB Output is correct
18 Correct 58 ms 27740 KB Output is correct
19 Correct 59 ms 27856 KB Output is correct
20 Correct 59 ms 27872 KB Output is correct

Subtask #3
0.0 / 80.0

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