Submission #1166629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166629		aycnl	Amusement Park (JOI17_amusement_park)	C++20	82 / 100	16 ms	2120 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))

#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)

#define pb push_back
#define pf push_front

#define endl "\n"
#define oo (int)(998244353)
#define maxN 10005

#define l(s) s.length()

#define vi vector <int>
#define vii vector <ii>

#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)

#define EPS 1e-9
#define pi (acos(-1))
#define ll long long

vi Ke[maxN];
int g[maxN], Par[maxN];
vi ttt;

int FSet(int u) {
    return g[u] == u ? u : g[u] = FSet(g[u]);
}

void USet(int u, int v) {
    int fu = FSet(u), fv = FSet(v);
    if (fu == fv) return;
    g[fv] = fu;
    Ke[u].pb(v);
    Ke[v].pb(u);
}

void DFS(int u) {
    ttt.pb(u);
    for (int v : Ke[u]) if (v != Par[u]) {
        Par[v] = u;
        DFS(v);
    }
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    fto(i, 0, N-1) g[i] = i;
    fto(i, 0, M-1) USet(A[i], B[i]);
    Par[0] = -1;
    DFS(0);

    int i = 0;
    while (1) {
        if (i + 59 >= N) {
            fto(j, i, N-1) MessageBoard(ttt[j], 0);
            break;
        }

        int ok = 1;
        fto(j, i+1, i + 59) {
            int ko = 0;
            fto(k, i, j-1) if (Par[ttt[j]] == ttt[k]) {
                ko = 1;
                break;
            }
            if (ko == 0) {
                ok = 0;
                break;
            }
        }

        if (!ok) {
            MessageBoard(ttt[i], 0);
            ++i;
            continue;
        }

        fto(j, 0, 59) MessageBoard(ttt[i+j], ((X&(1LL << j)) > 0));
        i += 60;
    }
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))

#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)

#define pb push_back
#define pf push_front

#define endl "\n"
#define oo (int)(998244353)
#define maxN 10005

#define l(s) s.length()

#define vi vector <int>
#define vii vector <ii>

#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)

#define EPS 1e-9
#define pi (acos(-1))
#define ll long long

int n, m, p;
vi ke[maxN];
int s[maxN], par[maxN];
int col[maxN], pos[maxN], id[maxN];
vi tt;

int fSet(int u) {
    return s[u] == u ? u : s[u] = fSet(s[u]);
}

void uSet(int u, int v) {
    int fu = fSet(u), fv = fSet(v);
    if (fu == fv) return;
    s[fv] = fu;
    ke[u].pb(v);
    ke[v].pb(u);
}

void dfs(int u) {
    pos[u] = (int)(tt.size());
    tt.pb(u);
    for (int v : ke[u]) if (v != par[u]) {
        par[v] = u;
        dfs(v);
    }
}

int moveto(int u) {
    if (u == 0) {
        int res = 0;
        while (p) {
            res = Move(par[p]);
            p = par[p];
        }
        return res;
    }

    while (par[u] != p) {
        Move(par[p]);
        p = par[p];
    }

    int res = Move(u);
    p = u;
    return res;
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    fto(i, 0, N-1) s[i] = i;
    fto(i, 0, M-1) uSet(A[i], B[i]);
    par[0] = -1;
    dfs(0);

    int i = 0, tme = 0;
    while (1) {
        if (i + 59 >= N) {
            fto(j, i, N-1) col[tt[j]] = -1;
            break;
        }

        int ok = 1;
        fto(j, i+1, i + 59) {
            int ko = 0;
            fto(k, i, j-1) if (par[tt[j]] == tt[k]) {
                ko = 1;
                break;
            }
            if (ko == 0) {
                ok = 0;
                break;
            }
        }

        if (!ok) {
            col[tt[i]] = -1;
            ++i;
            continue;
        }

        ++tme;
        fto(j, 0, 59) col[tt[i+j]] = 1, id[i+j] = tme;
        i += 60;
    }

    while (col[P] == -1) {
        V = Move(par[P]);
        P = par[P];
    }

    vi cur;
    fto(i, 0, N-1) if (id[i] == id[pos[P]]) cur.pb(tt[i]);

    int now = 0;
    fto(i, 0, 59) if (cur[i] == P) now = i;
    p = P;

    ll res = (1LL << now)*V;
    fto(i, 1, 59) {
        now = (now + 1)%60;
        res += (1LL << now)*moveto(cur[now]);
    }

    return res;
}

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