Submission #1171880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171880		browntoad	Amusement Park (JOI17_amusement_park)	C++20	100 / 100	18 ms	2908 KiB

Joi

#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define ppp pair<pii, pii>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

static const ll maxn = 1e4+5;

static vector<int> g[maxn], G[maxn]; // 0-base
static vector<pii> mxdep(maxn);
static vector<int> sz(maxn), dfsord(maxn);

static vector<bool> occ(maxn);
static void findtree(int u){
    occ[u] = 1;
    for (auto v:G[u]){
        if (occ[v]) continue;
        g[u].pb(v);
        g[v].pb(u);
        findtree(v);
    }
}

static void findd(int u, int pre){
    mxdep[u] = {0, -1};
    sz[u] = 1;
    for (auto v:g[u]){
        if (v == pre) continue;
        findd(v, u);
        if (mxdep[v].f+1 > mxdep[u].f){
            mxdep[u].f = mxdep[v].f+1;
            mxdep[u].s = v;
        }
        sz[u] += sz[v];
    }
}

static void dfs(int u, int pre, int &pus, ll X){
    dfsord[u] = pus++;
    MessageBoard(u, ((X&(1ll<<(dfsord[u]%60))) > 0));

    if (mxdep[u].s != -1) dfs(mxdep[u].s, u, pus, X);
    for (auto v:g[u]){
        if (v == pre || v == mxdep[u].s) continue;
        dfs(v, u, pus, X);
    }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    REP(i, M){
        G[A[i]].pb(B[i]);
        G[B[i]].pb(A[i]);
    }
    findtree(0);
    findd(0, -1);

    int pp = 0;
    dfs(0, -1, pp, X);
}

Ioi

#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define ppp pair<pii, pii>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

static const ll maxn = 1e4+5;

static vector<int> g[maxn], G[maxn]; // 0-base
static vector<pii> mxdep(maxn);
static vector<int> sz(maxn), dfsord(maxn), par(maxn);

static vector<bool> occ(maxn);
static void findtree(int u){
    occ[u] = 1;
    for (auto v:G[u]){
        if (occ[v]) continue;
        g[u].pb(v);
        g[v].pb(u);
        findtree(v);
    }
}

static void findd(int u, int pre){
    par[u] = pre;
    mxdep[u] = {0, -1};
    sz[u] = 1;
    for (auto v:g[u]){
        if (v == pre) continue;
        findd(v, u);
        if (mxdep[v].f+1 > mxdep[u].f){
            mxdep[u].f = mxdep[v].f+1;
            mxdep[u].s = v;
        }
        sz[u] += sz[v];
    }
}

static void dfs(int u, int pre, int &pus){
    dfsord[u] = pus++;
    // MessageBoard(u, (X&(1ll<<(dfsord[u]%60))));

    if (mxdep[u].s != -1) dfs(mxdep[u].s, u, pus);
    for (auto v:g[u]){
        if (v == pre || v == mxdep[u].s) continue;
        dfs(v, u, pus);
    }
}

static ll myX = 0;
static void runback(int u, int pre, int iord){
    if (dfsord[u] - iord >= 60) return;
    int ret = Move(u);
    myX += (1ll<<(dfsord[u]%60))*ret;

    for (auto v:g[u]){
        if (v == pre) continue;
        runback(v, u, iord);
    }
    Move(pre);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    REP(i, M){
        G[A[i]].pb(B[i]);
        G[B[i]].pb(A[i]);
    }
    findtree(0);
    findd(0, -1);

    int pp = 0;
    dfs(0, -1, pp);

    int cur = P, ret;
    while (sz[cur] < 60){
        cur = par[cur];
        ret = Move(cur);
    }
    if (cur == P){
        myX += (1ll<<(dfsord[cur]%60))*V;
    }
    else{
        myX += (1ll<<(dfsord[cur]%60))*ret;
    }

    int iord = dfsord[cur];
    while(cur != -1){
        for (auto v:g[cur]){
            if (v != par[cur] && v != mxdep[cur].s){
                runback(v, cur, iord);
            }
        }
        if (mxdep[cur].s != -1 && dfsord[mxdep[cur].s] - iord < 60){
            cur = mxdep[cur].s;
            ret = Move(cur);
            myX += (1ll<<(dfsord[cur]%60))*ret;
        }
        else break;
    }

    return myX;
}

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