Submission #491280

#	Time	Username	Problem	Language	Result	Execution time	Memory
491280		blue	Amusement Park (JOI17_amusement_park)	C++17	18 / 100	27 ms	4984 KiB

Joi

#include "Joi.h"
#include <vector>
using namespace std;

using vi = vector<int>;
using ll = long long;

static const int maxN = 10'000;

static vi edge[maxN];

static vi parent(maxN);
static vi children[maxN];

static const int lg = 60;

static int ct = -1;
static vi bits(lg);

static vi visit(maxN, 0);

static void dfs(int u)
{
    ct = (ct + 1) % lg;
    MessageBoard(u, bits[ct]);
    visit[u] = 1;

    for(int v: edge[u])
    {
        if(visit[v]) continue;
        dfs(v);
    }
}

void Joi(int N, int M, int A[], int B[], ll X, int T)
{
    for(int e = 0; e < lg; e++)
    {
        bits[e] = X % 2LL;
        X /= 2LL;
    }

    for(int j = 0; j < M; j++)
    {
        edge[A[j]].push_back(B[j]);
        edge[B[j]].push_back(A[j]);
    }

    dfs(0);
}

Ioi

#include "Ioi.h"
#include <vector>
using namespace std;

using vi = vector<int>;
using ll = long long;

static const int maxN = 10'000;

static vi edge[maxN];

static vi parent(maxN, -1);
static vi children[maxN];

static const int lg = 60;

static int ct = -1;
static vi bits(lg);

static vi visit(maxN, 0);

static vi ind(maxN);

static void dfs(int u)
{
    ct = (ct + 1) % lg;
    ind[u] = ct;
    visit[u] = 1;

    for(int v: edge[u])
    {
        if(visit[v]) continue;
        parent[v] = u;
        children[u].push_back(v);
        dfs(v);
    }
}

ll X = 0;

ll pow2[lg];

static void setbit(int b, int v)
{
    if(v)
        X += pow2[b];
}

static int mv;

static int set_count = 0;

static void dfs2(int u)
{
    if(set_count >= 60) return;
    set_count++;

    setbit(ind[u], mv);
    for(int v: children[u])
    {
        mv = Move(v);
        dfs2(v);
        mv = Move(u);
    }
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    pow2[0] = 1;
    for(int e = 1; e < lg; e++)
        pow2[e] = 2LL * pow2[e-1];

    for(int j = 0; j < M; j++)
    {
        edge[A[j]].push_back(B[j]);
        edge[B[j]].push_back(A[j]);
    }

    dfs(0);


    while(P != 0)
    {
        mv = Move(parent[P]);
        P = parent[P];
    }

    dfs2(0);

    return X;
}

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