oj.uz

Submission #1070585

# Submission time Handle Problem Language Result Execution time Memory
1070585 2024-08-22T15:38:42 Z GrindMachine The Ties That Guide Us (CEOI23_incursion) C++17
30 / 100
 220 ms 10676 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

read the edi a long time ago, dont really remember much from there

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "incursion.h"

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
    // return {2, 2, 0};
    int n = sz(F)+1;
    vector<vector<int>> adj(n+5);
    for(auto [u,v] : F){
        adj[u].pb(v), adj[v].pb(u);
    }

    vector<int> par(n+5), subsiz(n+5);

    auto dfs = [&](int u, int p, auto &&dfs) -> void{
        par[u] = p;
        subsiz[u] = 1;
        trav(v,adj[u]){
            if(v == p) conts;
            dfs(v,u,dfs);
            subsiz[u] += subsiz[v];
        }
    };

    dfs(1,-1,dfs);

    vector<int> centroids;
    rep1(u,n){
        bool ok = true;
        trav(v,adj[u]){
            int s = subsiz[v];
            if(v == par[u]){
                s = n-subsiz[u];
            }
            if(s > n/2){
                ok = false;
            }
        }

        if(ok){
            centroids.pb(u);
        }
    }

    int siz = sz(centroids);
    assert(siz >= 1 and siz <= 2);

    auto can_reach = [&](int u, int p, auto &&can_reach) -> bool{
        bool ok = false;
        if(u == safe) ok = true;
        trav(v,adj[u]){
            if(v == p) conts;
            if(count(all(centroids),v)) conts;
            ok |= can_reach(v,u,can_reach);
        }
        return ok;
    };

    int r = -1;
    if(siz == 1){
        r = centroids[0];
    }
    else{
        rep(j,2){
            if(can_reach(centroids[j],-1,can_reach)){
                assert(r == -1);
                r = centroids[j];
            }
        }
    }

    assert(r != -1);
    dfs(r,-1,dfs);

    vector<int> ans(n);
    while(safe != -1){
        ans[safe-1] = 1;
        safe = par[safe];
    }

    return ans;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int cnt) {
    int n = sz(F)+1;
    vector<vector<int>> adj(n+5);
    for(auto [u,v] : F){
        adj[u].pb(v), adj[v].pb(u);
    }

    vector<int> par(n+5), subsiz(n+5);

    auto dfs = [&](int u, int p, auto &&dfs) -> void{
        par[u] = p;
        subsiz[u] = 1;
        trav(v,adj[u]){
            if(v == p) conts;
            dfs(v,u,dfs);
            subsiz[u] += subsiz[v];
        }
    };

    dfs(1,-1,dfs);

    vector<int> centroids;
    rep1(u,n){
        bool ok = true;
        trav(v,adj[u]){
            int s = subsiz[v];
            if(v == par[u]){
                s = n-subsiz[u];
            }
            if(s > n/2){
                ok = false;
            }
        }

        if(ok){
            centroids.pb(u);
        }
    }

    int siz = sz(centroids);
    assert(siz >= 1 and siz <= 2);

    int r = centroids[0];
    dfs(r,-1,dfs);

    if(siz == 1){
        while(!cnt){
            cnt = visit(par[curr]);
            curr = par[curr];
        }

        while(true){
            vector<pii> ord;
            trav(v,adj[curr]){
                if(v == par[curr]) conts;
                ord.pb({subsiz[v],v});
            }
            sort(rall(ord));

            int nxt = -1;
            for(auto [s,v] : ord){
                int x = visit(v);
                if(x){
                    nxt = v;
                    break;
                }
                visit(curr);
            }

            if(nxt == -1) break;
            curr = nxt;
        }

        return;
    }

    while(!cnt){
        if(count(all(centroids),curr)){
            break;
        }

        cnt = visit(par[curr]);
        curr = par[curr];
    }

    if(count(all(centroids),curr)){
        if(cnt){
            r = curr;
        }
        else{
            int other = curr^centroids[0]^centroids[1];
            r = curr = other;
            visit(r);
        }
    }

    dfs(r,-1,dfs);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    while(true){
        vector<pii> ord;
        map<int,vector<int>> mp;
        trav(v,adj[curr]){
            if(v == par[curr] or count(all(centroids),v)) conts;
            mp[subsiz[v]].pb(v);
        }

        for(auto it = mp.rbegin(); it != mp.rend(); ++it){
            shuffle(all(it->ss),rng);
            trav(v,it->ss) ord.pb({subsiz[v],v});
        }

        int nxt = -1;
        for(auto [s,v] : ord){
            int x = visit(v);
            if(x){
                nxt = v;
                break;
            }
            visit(curr);
        }

        if(curr == r and nxt == -1){
            nxt = r^centroids[0]^centroids[1];
            visit(nxt);
        }

        if(nxt == -1) break;
        curr = nxt;
    }

    // int x;
    // x = visit(3);
    // if (x != 2) {
    //     return;
    // }
    // x = visit(1);
    // if (x != 0) {
    //     return;
    // }
    // x = visit(3);
    // if (x != 2) {
    //     return;
    // }
    // x = visit(2);
    // if (x != 2) {
    //     return;
    // }
    // return;
}

Compilation message

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 768 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 9952 KB Correct
2 Correct 208 ms 10012 KB Correct
3 Correct 119 ms 10676 KB Correct
4 Correct 139 ms 10544 KB Correct
5 Correct 215 ms 10572 KB Correct
6 Incorrect 98 ms 10536 KB Not correct
7 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 7868 KB Correct
2 Correct 113 ms 7936 KB Correct
3 Correct 93 ms 7948 KB Correct
4 Correct 99 ms 9488 KB Correct
5 Correct 156 ms 9016 KB Correct
6 Correct 175 ms 8948 KB Correct
7 Correct 89 ms 7584 KB Correct
8 Correct 86 ms 7760 KB Correct
9 Correct 83 ms 7768 KB Correct
10 Correct 68 ms 7780 KB Correct
11 Correct 84 ms 7672 KB Correct
12 Correct 68 ms 7752 KB Correct
13 Correct 83 ms 7684 KB Correct
14 Correct 61 ms 5876 KB Correct
15 Correct 59 ms 5888 KB Correct
16 Correct 81 ms 7664 KB Correct
17 Correct 92 ms 7520 KB Correct
18 Correct 74 ms 7676 KB Correct
19 Correct 78 ms 7516 KB Correct
20 Correct 69 ms 5788 KB Correct
21 Correct 50 ms 5968 KB Correct
22 Correct 53 ms 5788 KB Correct
23 Correct 68 ms 5868 KB Correct
24 Correct 65 ms 6156 KB Correct
25 Correct 51 ms 5892 KB Correct
26 Correct 87 ms 8020 KB Correct
27 Correct 75 ms 7916 KB Correct
28 Correct 83 ms 8012 KB Correct
29 Correct 81 ms 8096 KB Correct
30 Correct 88 ms 8044 KB Correct
31 Correct 80 ms 7836 KB Correct
32 Correct 91 ms 7692 KB Correct
33 Correct 83 ms 7916 KB Correct
34 Correct 100 ms 7784 KB Correct
35 Correct 95 ms 7756 KB Correct
36 Correct 74 ms 7944 KB Correct
37 Correct 78 ms 7752 KB Correct
38 Correct 69 ms 7860 KB Correct
39 Correct 83 ms 8020 KB Correct
40 Correct 95 ms 8264 KB Correct
41 Correct 87 ms 7924 KB Correct
42 Correct 100 ms 8028 KB Correct
43 Correct 96 ms 7776 KB Correct
44 Correct 90 ms 8044 KB Correct
45 Correct 93 ms 7828 KB Correct
46 Correct 87 ms 7948 KB Correct
47 Correct 98 ms 7936 KB Correct
48 Correct 92 ms 8040 KB Correct
49 Correct 83 ms 7676 KB Correct
50 Correct 81 ms 7928 KB Correct
51 Correct 84 ms 7932 KB Correct
52 Correct 98 ms 8056 KB Correct
53 Correct 81 ms 7696 KB Correct
54 Correct 100 ms 8064 KB Correct
55 Correct 84 ms 7668 KB Correct
56 Correct 86 ms 7940 KB Correct
57 Correct 79 ms 7724 KB Correct
58 Correct 89 ms 7924 KB Correct
59 Correct 82 ms 8012 KB Correct
60 Correct 78 ms 7948 KB Correct
61 Correct 90 ms 7924 KB Correct
62 Correct 83 ms 8024 KB Correct
63 Correct 88 ms 7928 KB Correct
64 Correct 77 ms 7764 KB Correct
65 Correct 83 ms 7836 KB Correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 768 KB Correct
2 Correct 220 ms 9952 KB Correct
3 Correct 208 ms 10012 KB Correct
4 Correct 119 ms 10676 KB Correct
5 Correct 139 ms 10544 KB Correct
6 Correct 215 ms 10572 KB Correct
7 Incorrect 98 ms 10536 KB Not correct
8 Halted 0 ms 0 KB -