oj.uz

Submission #959854

# Submission time Handle Problem Language Result Execution time Memory
959854 2024-04-09T08:34:54 Z mansur Newspapers (CEOI21_newspapers) C++17
6 / 100
 65 ms 28060 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 <= 10) {
		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 6 ms 27608 KB Output is correct
3 Correct 8 ms 27740 KB Output is correct
4 Correct 7 ms 27740 KB Output is correct
5 Correct 7 ms 27744 KB Output is correct
6 Correct 7 ms 27740 KB Output is correct
7 Correct 6 ms 27740 KB Output is correct
8 Correct 7 ms 27740 KB Output is correct
9 Correct 8 ms 27740 KB Output is correct
10 Correct 7 ms 27620 KB Output is correct
11 Correct 7 ms 27736 KB Output is correct
12 Correct 9 ms 27740 KB Output is correct
13 Correct 7 ms 27616 KB Output is correct
14 Correct 7 ms 27740 KB Output is correct
15 Correct 7 ms 27740 KB Output is correct
16 Correct 8 ms 27740 KB Output is correct
17 Correct 7 ms 27736 KB Output is correct
18 Correct 7 ms 27740 KB Output is correct
19 Partially correct 8 ms 27652 KB Failed to provide a successful strategy.
20 Partially correct 7 ms 27740 KB Failed to provide a successful strategy.
21 Partially correct 6 ms 27740 KB Provide a successful but not optimal strategy.
22 Partially correct 7 ms 27740 KB Failed to provide a successful strategy.
23 Partially correct 6 ms 27732 KB Failed to provide a successful strategy.
24 Partially correct 6 ms 27740 KB Failed to provide a successful strategy.
25 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
26 Partially correct 8 ms 27740 KB Failed to provide a successful strategy.
27 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
28 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
29 Incorrect 8 ms 27736 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #2
6.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27736 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 7 ms 27740 KB Output is correct
6 Correct 8 ms 27740 KB Output is correct
7 Correct 7 ms 27736 KB Output is correct
8 Correct 8 ms 27740 KB Output is correct
9 Correct 7 ms 27740 KB Output is correct
10 Partially correct 6 ms 27740 KB Provide a successful but not optimal strategy.
11 Correct 53 ms 27740 KB Output is correct
12 Correct 25 ms 27996 KB Output is correct
13 Correct 27 ms 27740 KB Output is correct
14 Correct 30 ms 27736 KB Output is correct
15 Correct 36 ms 27980 KB Output is correct
16 Correct 60 ms 28060 KB Output is correct
17 Correct 59 ms 27856 KB Output is correct
18 Correct 59 ms 27740 KB Output is correct
19 Correct 65 ms 27828 KB Output is correct
20 Correct 60 ms 27740 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 6 ms 27608 KB Output is correct
3 Correct 8 ms 27740 KB Output is correct
4 Correct 7 ms 27740 KB Output is correct
5 Correct 7 ms 27744 KB Output is correct
6 Correct 7 ms 27740 KB Output is correct
7 Correct 6 ms 27740 KB Output is correct
8 Correct 7 ms 27740 KB Output is correct
9 Correct 8 ms 27740 KB Output is correct
10 Correct 7 ms 27620 KB Output is correct
11 Correct 7 ms 27736 KB Output is correct
12 Correct 9 ms 27740 KB Output is correct
13 Correct 7 ms 27616 KB Output is correct
14 Correct 7 ms 27740 KB Output is correct
15 Correct 7 ms 27740 KB Output is correct
16 Correct 8 ms 27740 KB Output is correct
17 Correct 7 ms 27736 KB Output is correct
18 Correct 7 ms 27740 KB Output is correct
19 Partially correct 8 ms 27652 KB Failed to provide a successful strategy.
20 Partially correct 7 ms 27740 KB Failed to provide a successful strategy.
21 Partially correct 6 ms 27740 KB Provide a successful but not optimal strategy.
22 Partially correct 7 ms 27740 KB Failed to provide a successful strategy.
23 Partially correct 6 ms 27732 KB Failed to provide a successful strategy.
24 Partially correct 6 ms 27740 KB Failed to provide a successful strategy.
25 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
26 Partially correct 8 ms 27740 KB Failed to provide a successful strategy.
27 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
28 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
29 Incorrect 8 ms 27736 KB Output isn't correct
30 Halted 0 ms 0 KB -