oj.uz

Submission #986255

# Submission time Handle Problem Language Result Execution time Memory
986255 2024-05-20T07:11:47 Z nextgenxing Newspapers (CEOI21_newspapers) C++14
20 / 100
 6 ms 19036 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define F0Rd(i, x) FORd(i, 0, x)
#define ckif(a, b, c) ((c) ? (a) : (b))
const int MAX_N = 2e5+69;
const ll MOD = 1000000007;
const ll INF = 1e18;

int n, m;
vector<int> adj[MAX_N];
int anc[MAX_N][20], dep[MAX_N], vis[MAX_N];
int dis[1048576], lst[1048576], mv[1048576];
pii mx[MAX_N], mx2[MAX_N];
pair<int, pii> diam[MAX_N];

bool dfs(int curr, int par = -1){
    vis[curr] = 1, mx[curr] = {0, curr};
    for(auto x : adj[curr]){
        if(x == par) continue;
        if(vis[x]) return false;
        anc[x][0] = curr;
        dep[x] = dep[curr]+1;
        if(!dfs(x, curr)) return false;
        if(mx[x].ff+1 >= mx[curr].ff) mx2[curr] = mx[curr], mx[curr] = mx[x], mx[curr].ff++;
        else if(mx[x].ff+1 >= mx2[curr].ff) mx2[curr] = mx[x], mx2[curr].ff++;
        if(diam[x].ff >= diam[curr].ff) diam[curr] = diam[x];
    }
    if(mx[curr].ff+mx2[curr].ff >= diam[curr].ff) diam[curr] = {mx[curr].ff+mx2[curr].ff, {mx[curr].ss, mx2[curr].ss}};
    return true;
}

int lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    F0Rd(i, 20) if(dep[a]+(1 << i) <= dep[b])
        b = anc[b][i];
    if(a == b) return a;
    F0Rd(i, 20) if(anc[a][i] != anc[b][i])
        a = anc[a][i], b = anc[b][i];
    return anc[a][0];
}

int dist(int a, int b){
    return dep[lca(a, b)]*2-dep[a]-dep[b];
}

int main(int argc, const char * argv[]){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> m;
    F0R(i, m){
        int a, b; cin >> a >> b; a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    if(n <= 20){
        queue<pii> q; q.push({(1 << n)-1, 0});
        while(!q.empty()){
            int x = q.front().ff, d = q.front().ss, y = 0; q.pop();
            F0R(i, n) if(x&(1 << i)) for(auto z : adj[i])
                y |= (1 << z);
            F0R(i, n){
                int z = y; if(z&(1 << i)) z ^= (1 << i);
                if(dis[z]) continue;
                dis[z] = d+1, lst[z] = x, mv[z] = i+1;
                q.push({z, d+1});
            }
        }
        if(!dis[0]){
            cout << "NO\n";
            return 0;
        }
        cout << "YES\n" << dis[0] << '\n';
        vector<int> nums;
        for(int x = 0; x < (1 << n)-1; x = lst[x])
            nums.push_back(mv[x]);
        reverse(all(nums));
        for(auto x : nums) cout << x << ' ';
        cout << '\n';
        return 0;
    }
    if(!dfs(0)){
        cout << "NO\n";
        return 0;
    }
    FOR(d, 1, 20) F0R(i, n)
        anc[i][d] = anc[anc[i][d-1]][d-1];
    int a = diam[0].ss.ff, b = diam[0].ss.ss, c = lca(a, b);
    F0R(i, n){
        int x = c^lca(a, i)^lca(b, i);
        if(dist(i, x) > 2){
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
    if(dep[a] < dep[b]) swap(a, b);
    vector<int> seq, seq2;
    while(anc[a][0] != c){
        int tmp = a; a = anc[a][0];
        seq.push_back(a);
        for(auto x : adj[a]) if(x != tmp && x != anc[a][0])
            seq.push_back(x), seq.push_back(a);
    }
    while(anc[b][0] != c){
        int tmp = b; b = anc[b][0];
        seq2.push_back(b);
        for(auto x : adj[b]) if(x != tmp && x != anc[b][0])
            seq2.push_back(x), seq2.push_back(b);
    }
    if(b != c){
        seq.push_back(c);
        for(auto x : adj[c]) if(x != a && x != b)
            seq.push_back(x), seq.push_back(c);
        reverse(all(seq2));
        for(auto x : seq2) seq.push_back(x);
    }
    cout << 2*seq.size() << '\n';
    for(auto x : seq) cout << x+1 << ' ';
    reverse(all(seq));
    for(auto x : seq) cout << x+1 << ' ';
    cout << '\n';
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 11096 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11128 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11352 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11280 KB Output is correct
11 Correct 2 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 2 ms 11284 KB Output is correct
14 Correct 2 ms 11100 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 2 ms 11100 KB Output is correct
17 Correct 2 ms 11096 KB Output is correct
18 Correct 2 ms 11100 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 6 ms 11100 KB Output is correct
24 Correct 3 ms 11096 KB Output is correct
25 Correct 2 ms 11100 KB Output is correct
26 Correct 2 ms 11284 KB Output is correct
27 Correct 2 ms 11096 KB Output is correct
28 Correct 3 ms 11100 KB Output is correct
29 Correct 2 ms 11100 KB Output is correct
30 Correct 3 ms 11096 KB Output is correct
31 Correct 2 ms 11352 KB Output is correct
32 Correct 2 ms 11352 KB Output is correct
33 Correct 2 ms 11356 KB Output is correct
34 Correct 2 ms 11100 KB Output is correct
35 Correct 2 ms 11356 KB Output is correct
36 Correct 2 ms 11608 KB Output is correct
37 Correct 2 ms 11552 KB Output is correct
38 Correct 2 ms 11356 KB Output is correct
39 Correct 2 ms 11400 KB Output is correct
40 Correct 3 ms 11356 KB Output is correct
41 Correct 2 ms 11356 KB Output is correct
42 Correct 2 ms 11356 KB Output is correct
43 Correct 3 ms 11612 KB Output is correct
44 Correct 3 ms 11700 KB Output is correct
45 Correct 3 ms 11540 KB Output is correct
46 Correct 2 ms 11612 KB Output is correct
47 Correct 3 ms 15964 KB Output is correct
48 Correct 3 ms 16220 KB Output is correct
49 Correct 3 ms 15964 KB Output is correct
50 Correct 4 ms 15964 KB Output is correct
51 Correct 4 ms 16732 KB Output is correct
52 Correct 4 ms 15960 KB Output is correct
53 Correct 3 ms 16220 KB Output is correct
54 Correct 4 ms 16400 KB Output is correct
55 Correct 3 ms 18520 KB Output is correct
56 Correct 4 ms 18012 KB Output is correct
57 Correct 4 ms 19036 KB Output is correct
58 Correct 4 ms 18524 KB Output is correct
59 Correct 3 ms 15196 KB Output is correct
60 Correct 3 ms 15196 KB Output is correct
61 Correct 3 ms 15452 KB Output is correct
62 Correct 3 ms 15196 KB Output is correct
63 Correct 3 ms 15196 KB Output is correct
64 Correct 3 ms 15196 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11096 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 2 ms 11352 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11200 KB Output is correct
11 Correct 3 ms 13404 KB Output is correct
12 Correct 3 ms 13404 KB Output is correct
13 Correct 3 ms 13400 KB Output is correct
14 Correct 3 ms 13404 KB Output is correct
15 Correct 3 ms 13404 KB Output is correct
16 Correct 3 ms 13404 KB Output is correct
17 Correct 3 ms 13404 KB Output is correct
18 Correct 3 ms 13400 KB Output is correct
19 Correct 3 ms 13400 KB Output is correct
20 Correct 3 ms 13400 KB Output is correct

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 11096 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 2 ms 11128 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11352 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11280 KB Output is correct
11 Correct 2 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 2 ms 11284 KB Output is correct
14 Correct 2 ms 11100 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 2 ms 11100 KB Output is correct
17 Correct 2 ms 11096 KB Output is correct
18 Correct 2 ms 11100 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 2 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 11100 KB Output is correct
23 Correct 6 ms 11100 KB Output is correct
24 Correct 3 ms 11096 KB Output is correct
25 Correct 2 ms 11100 KB Output is correct
26 Correct 2 ms 11284 KB Output is correct
27 Correct 2 ms 11096 KB Output is correct
28 Correct 3 ms 11100 KB Output is correct
29 Correct 2 ms 11100 KB Output is correct
30 Correct 3 ms 11096 KB Output is correct
31 Correct 2 ms 11352 KB Output is correct
32 Correct 2 ms 11352 KB Output is correct
33 Correct 2 ms 11356 KB Output is correct
34 Correct 2 ms 11100 KB Output is correct
35 Correct 2 ms 11356 KB Output is correct
36 Correct 2 ms 11608 KB Output is correct
37 Correct 2 ms 11552 KB Output is correct
38 Correct 2 ms 11356 KB Output is correct
39 Correct 2 ms 11400 KB Output is correct
40 Correct 3 ms 11356 KB Output is correct
41 Correct 2 ms 11356 KB Output is correct
42 Correct 2 ms 11356 KB Output is correct
43 Correct 3 ms 11612 KB Output is correct
44 Correct 3 ms 11700 KB Output is correct
45 Correct 3 ms 11540 KB Output is correct
46 Correct 2 ms 11612 KB Output is correct
47 Correct 3 ms 15964 KB Output is correct
48 Correct 3 ms 16220 KB Output is correct
49 Correct 3 ms 15964 KB Output is correct
50 Correct 4 ms 15964 KB Output is correct
51 Correct 4 ms 16732 KB Output is correct
52 Correct 4 ms 15960 KB Output is correct
53 Correct 3 ms 16220 KB Output is correct
54 Correct 4 ms 16400 KB Output is correct
55 Correct 3 ms 18520 KB Output is correct
56 Correct 4 ms 18012 KB Output is correct
57 Correct 4 ms 19036 KB Output is correct
58 Correct 4 ms 18524 KB Output is correct
59 Correct 3 ms 15196 KB Output is correct
60 Correct 3 ms 15196 KB Output is correct
61 Correct 3 ms 15452 KB Output is correct
62 Correct 3 ms 15196 KB Output is correct
63 Correct 3 ms 15196 KB Output is correct
64 Correct 3 ms 15196 KB Output is correct
65 Correct 2 ms 11096 KB Output is correct
66 Correct 2 ms 11100 KB Output is correct
67 Correct 2 ms 11096 KB Output is correct
68 Correct 2 ms 11100 KB Output is correct
69 Correct 2 ms 11100 KB Output is correct
70 Correct 2 ms 11100 KB Output is correct
71 Correct 2 ms 11100 KB Output is correct
72 Correct 2 ms 11100 KB Output is correct
73 Correct 2 ms 11100 KB Output is correct
74 Correct 2 ms 11100 KB Output is correct
75 Correct 2 ms 11100 KB Output is correct
76 Correct 2 ms 11100 KB Output is correct
77 Correct 2 ms 11100 KB Output is correct
78 Correct 2 ms 11100 KB Output is correct
79 Incorrect 3 ms 13148 KB Output isn't correct
80 Halted 0 ms 0 KB -