Submission #1146665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146665		_8_8_	Amusement Park (JOI17_amusement_park)	C++20	10 / 100	148 ms	166744 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int)1e5 + 12, b = 60;

mt19937 rng1(123321);
vector<int> g1[N], G1[N];
int tin1[N], timer1, va[N], pr1[N];
bool vis1[N], ok1[N];
ll x;

void build1(int n) {
    set<int> cur;

    function<void(int)> dd = [&](int v) {
        vis1[v] = 1;
        for(int to : g1[v]) {
            if(!vis1[to]) {
                dd(to);
                pr1[to] = v;
                G1[v].push_back(to);
            }
        }
    };
    function<void(int)> dfs = [&](int v){
        vis1[v] = 1;
        cur.insert(v);
        if((int)cur.size() == b) return;
        for(int to : G1[v]) {
            if(!vis1[to]) {
                dfs(to);
                if((int)cur.size() == b) return;
            }
        }
    };
    auto find = [&](int bl) {
        for(int i : cur) {
            if(i == bl) continue;
            int col = 0;
            for(int to : G1[i]) {
                if(ok1[to]) {
                    col++;
                }
            }
            if(i && ok1[pr1[i]]) col++;
            if(col == 1) return i;
        }
        exit(-1);
    };
    function<void(int, int)> go = [&](int v, int pr) {
        for(int to : G1[v]) {
            int del = -1;
            if(!ok1[to]) {
                del = find(v);
                ok1[del] = 0;
                ok1[to] = 1;
                cur.erase(del);
                cur.insert(to);
                va[to] = va[del];
            }
            go(to, v);
            if(!ok1[to]) {
                ok1[del] = 1;
                ok1[to] = 0;
                cur.insert(del);
                cur.erase(to);
            }
        }
    };
    dd(0);
    for(int i = 0; i < n; i++) {
        vis1[i] = 0;
    }
    dfs(0);
    auto it = (cur.begin());
    for(int i = 0; i < b; i++) {
        ok1[(*it)] = 1;
        va[(*it)] = i;
        it++;
    }
    go(0, -1);

    for(int i = 0; i < n; i++) {
        MessageBoard(i, ((x >> va[i]) & 1));
    }
}
void Joi(int n, int m, int A[], int B[], long long X, int T) {
    x = X;
    for(int i = 0; i < m; i++) {
        g1[A[i]].push_back(B[i]);
        g1[B[i]].push_back(A[i]);
    }
    for(int i = 0; i < n; i++) {
        sort(g1[i].begin(), g1[i].end());
    }
    build1(n);
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = (int)1e5 + 12, b = 60;

mt19937 rng(123321);
ll d[N], mxd[N], pr[N], timer, sz[N];
vector<int> g[N], G[N];
int tin[N], bt[N], tout[N], val[N];
bool vis[N], ok[N];
set<int> st[N];
void build(int n) {
    set<int> cur;
    function<void(int)> dd = [&](int v) {
        vis[v] = 1;
        for(int to : g[v]) {
            if(!vis[to]) {
                pr[to] = v;
                dd(to);
                G[v].push_back(to);
            }
        }
    };
    function<void(int)> dfs = [&](int v){
        vis[v] = 1;
        cur.insert(v);
        if((int)cur.size() == b) return;
        for(int to : G[v]) {
            if(!vis[to]) {
                dfs(to);
                if((int)cur.size() == b) return;
            }
        }
    };
    auto find = [&](int bl) {
        for(int i : cur) {
            if(i == bl) continue;
            int col = 0;
            for(int to : G[i]) {
                if(ok[to]) {
                    col++;
                }
            }
            if(i && ok[pr[i]]) col++;
            if(col == 1) return i;
        }
        exit(-1);
    };
    function<void(int, int)> go = [&](int v, int pr) {
        for(int to : G[v]) {
            int del = -1;
            if(!ok[to]) {
                del = find(v);
                ok[del] = 0;
                ok[to] = 1;
                cur.erase(del);
                cur.insert(to);
                val[to] = val[del];
                st[to] = cur;
            }
            go(to, v);
            if(!ok[to]) {
                ok[del] = 1;
                ok[to] = 0;
                cur.insert(del);
                cur.erase(to);
            }
        }
    };
    dd(0);
    for(int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    dfs(0);
    auto it = (cur.begin());
    for(int i = 0; i < b; i++) {
        st[(*it)] = cur;
        ok[(*it)] = 1;
        val[(*it)] = i;
        it++;
    }
    go(0, -1);
}
long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
    memset(pr, -1, sizeof(pr));
    for(int i = 0; i < m; i++) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    for(int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end());
    }
    build(n);
    int cur = P;
    function<void(int, int, int)> dfs = [&](int v, int pr, int f) {
        bt[val[v]] = f;
        ok[v] = 0;
        assert(cur == v);
        for(int to : G[v]) {
            if(ok[to] && to != pr) {
                cur = to;
                dfs(to, v, Move(to));
                assert(cur == v);
            }
        }
        if(pr != -1) {
            cur = pr;
            Move(pr);
        }
    };
    for(int i = 0; i < n; i++) {
        ok[i] = 0;
        if(pr[i] != -1) {
            G[i].push_back(pr[i]);
        }
    }
    for(int i = 0; i < n; i++) {
        sort(G[i].begin(), G[i].end());
        assert(G[i] == g[i]);
    }
    for(int j : st[P]) {
        ok[j] = 1;
    }
    dfs(P, -1, V);
    ll res = 0;
    for(int i = 0; i < b; i++) {
        if(bt[i]) res += (1ll << i);
    }
    return res;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17