oj.uz

Submission #959850

# Submission time Handle Problem Language Result Execution time Memory
959850 2024-04-09T08:34:09 Z mansur Newspapers (CEOI21_newspapers) C++17
8 / 100
 59 ms 27872 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 <= 5) {
		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 27740 KB Output is correct
2 Correct 7 ms 27736 KB Output is correct
3 Correct 7 ms 27632 KB Output is correct
4 Correct 6 ms 27740 KB Output is correct
5 Correct 6 ms 27740 KB Output is correct
6 Partially correct 6 ms 27740 KB Failed to provide a successful strategy.
7 Correct 7 ms 27740 KB Output is correct
8 Partially correct 7 ms 27740 KB Failed to provide a successful strategy.
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 6 ms 27740 KB Output is correct
2 Correct 6 ms 27740 KB Output is correct
3 Correct 7 ms 27740 KB Output is correct
4 Correct 7 ms 27740 KB Output is correct
5 Correct 6 ms 27740 KB Output is correct
6 Correct 7 ms 27612 KB Output is correct
7 Correct 7 ms 27740 KB Output is correct
8 Correct 6 ms 27740 KB Output is correct
9 Correct 7 ms 27740 KB Output is correct
10 Correct 6 ms 27740 KB Output is correct
11 Correct 53 ms 27824 KB Output is correct
12 Correct 21 ms 27740 KB Output is correct
13 Correct 26 ms 27736 KB Output is correct
14 Correct 31 ms 27844 KB Output is correct
15 Correct 31 ms 27740 KB Output is correct
16 Correct 58 ms 27872 KB Output is correct
17 Correct 58 ms 27736 KB Output is correct
18 Correct 57 ms 27868 KB Output is correct
19 Correct 59 ms 27852 KB Output is correct
20 Correct 59 ms 27856 KB Output is correct

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27740 KB Output is correct
2 Correct 7 ms 27736 KB Output is correct
3 Correct 7 ms 27632 KB Output is correct
4 Correct 6 ms 27740 KB Output is correct
5 Correct 6 ms 27740 KB Output is correct
6 Partially correct 6 ms 27740 KB Failed to provide a successful strategy.
7 Correct 7 ms 27740 KB Output is correct
8 Partially correct 7 ms 27740 KB Failed to provide a successful strategy.
9 Incorrect 7 ms 27740 KB Output isn't correct
10 Halted 0 ms 0 KB -