oj.uz

Submission #959848

# Submission time Handle Problem Language Result Execution time Memory
959848 2024-04-09T08:33:30 Z mansur Newspapers (CEOI21_newspapers) C++17
8 / 100
 60 ms 28004 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 <= 2) {
		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 10 ms 27736 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 6 ms 27740 KB Output is correct
4 Correct 6 ms 27740 KB Output is correct
5 Partially correct 7 ms 27624 KB Failed to provide a successful strategy.
6 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
7 Correct 6 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 27736 KB Output is correct
2 Correct 6 ms 27740 KB Output is correct
3 Correct 6 ms 27572 KB Output is correct
4 Correct 7 ms 27608 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 6 ms 27740 KB Output is correct
9 Correct 6 ms 27740 KB Output is correct
10 Correct 6 ms 27740 KB Output is correct
11 Correct 53 ms 27868 KB Output is correct
12 Correct 21 ms 27808 KB Output is correct
13 Correct 27 ms 27736 KB Output is correct
14 Correct 32 ms 28004 KB Output is correct
15 Correct 30 ms 27740 KB Output is correct
16 Correct 58 ms 27936 KB Output is correct
17 Correct 58 ms 28000 KB Output is correct
18 Correct 58 ms 27992 KB Output is correct
19 Correct 60 ms 27984 KB Output is correct
20 Correct 58 ms 27736 KB Output is correct

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 27736 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 6 ms 27740 KB Output is correct
4 Correct 6 ms 27740 KB Output is correct
5 Partially correct 7 ms 27624 KB Failed to provide a successful strategy.
6 Partially correct 7 ms 27736 KB Failed to provide a successful strategy.
7 Correct 6 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 -