Submission #41832

#	Time	Username	Problem	Language	Result	Execution time	Memory
41832		krauch	Amusement Park (JOI17_amusement_park)	C++14	82 / 100	40 ms	5384 KiB

Joi

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

using namespace std;

typedef long long ll;

#define eb emplace_back
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

static const int MAXN = 2e4 + 6;

static int n, m, comp[MAXN], cnt;
static ll X, sz[MAXN];
static vector < int > g[MAXN];
static bool u[MAXN];

void dfs(int v) {
    u[v] = 1;
    for (auto to : g[v]) {
        if (u[to]) continue;
        if (sz[comp[v]] == 60)
            comp[to] = ++cnt;
        else
            comp[to] = comp[v];
        MessageBoard(to - 1, (X >> sz[comp[to]]) & 1);
        sz[comp[to]]++;
        dfs(to);
    }
}

void Joi(int _n, int _m, int A[], int B[], long long _x, int _t) {
    n = _n, m = _m;
    int Root = (n < 132 ? 58 : 132);
    X = _x;
    forn(i, 0, m - 1) {
        A[i]++, B[i]++;
        g[A[i]].eb(B[i]);
        g[B[i]].eb(A[i]);
    }

    cnt = 1;
    comp[Root] = 1;
    sz[comp[Root]] = 1;
    MessageBoard(Root - 1, X & 1);
    dfs(Root);
    forn(i, 0, m - 1)
        --A[i], --B[i];
}


#ifdef krauch
int main() {
    return 0;
}
#endif

Ioi

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

using namespace std;

typedef long long ll;

#define eb emplace_back
#define sz(a) (int)a.size()
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

static const int MAXN = 2e4 + 6;

static int n, m, comp[MAXN], cnt, par[MAXN], CUR;
static ll X, sz[MAXN], lvl[MAXN], ans[66];
static vector < int > g[MAXN];
static bool u[MAXN];

void dfs(int v) {
    CUR++;
    u[v] = 1;
    for (auto to : g[v]) {
        if (u[to]) continue;
        if (sz[comp[v]] == 60)
            comp[to] = ++cnt;
        else
            comp[to] = comp[v];
        lvl[to] = sz[comp[to]];
        sz[comp[to]]++;
        par[to] = v;
        dfs(to);
    }
}

void dfs2(int v, int val) {
    u[v] = 1;
    ans[lvl[v]] |= val;
    for (auto to : g[v]) {
        if (u[to] || comp[to] != comp[v]) continue;
        int toval = Move(to - 1);
        dfs2(to, toval);
        val = Move(v - 1);
    }
}

ll Ioi(int _n, int _m, int A[], int B[], int _p, int _v, int _t) {
    n = _n, m = _m;
    int Root = (n < 132 ? 58 : 132);
    int st = _p + 1, stval = _v;
    bool ok = 0;
    forn(i, 0, m - 1) {
        ++A[i], ++B[i];
        g[A[i]].eb(B[i]);
        g[B[i]].eb(A[i]);
    }

    cnt = 1;
    comp[Root] = 1;
    sz[comp[Root]] = 1;
    dfs(Root);

    while (sz[comp[st]] != 60) {
        st = par[st];
        stval = Move(st - 1);
    }
    forn(i, 1, n) u[i] = 0;
    dfs2(st, stval);

    ll res = 0;
    forn(i, 0, 60) {
        res |= (ans[i] << ll(i));
    }
    forn(i, 0, m - 1)
        --A[i], --B[i];
    return res;
}


#ifdef krauch
int main() {
    return 0;
}
#endif

Compilation message (stderr)

Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:51:10: warning: unused variable 'ok' [-Wunused-variable]
     bool ok = 0;
          ^
Ioi.cpp: At global scope:
Ioi.cpp:16:11: warning: 'X' defined but not used [-Wunused-variable]
 static ll X, sz[MAXN], lvl[MAXN], ans[66];
           ^

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