Submission #257347

#	Time	Username	Problem	Language	Result	Execution time	Memory
257347		imeimi2000	Snowy Roads (JOI16_snowy)	C++17	100 / 100	21 ms	2052 KiB

Anya

#include <bits/stdc++.h>

using namespace std;

void Save(int, int);

const static int mod = 12, lg = 9;
static int A[501], B[501], n;
static vector<int> edge[501];
static vector<int> D[mod];
static int par[501];

void dfs1(int x, int p, int d) {
    par[x] = p;
    if (d) D[d % mod].push_back(x);
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs1(i, x, d + 1);
    }
}

void InitAnya(int _n, int _A[], int _B[]) {
    n = _n;
    for (int i = 1; i < n; ++i) {
        A[i] = _A[i - 1] + 1;
        B[i] = _B[i - 1] + 1;
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    dfs1(1, 0, 0);
    for (int i = 1; i < n; ++i) {
        if (par[A[i]] == B[i]) swap(A[i], B[i]);
    }
    int mn = 0;
    for (int i = 1; i < mod; ++i) if (D[i].size() < D[mn].size()) mn = i;
    swap(D[0], D[mn]);
}

static int dist[501];
static int pdis[501];
void dfs2(int x, int p, int d) {
    dist[x] = d;
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs2(i, x, d + pdis[i]);
    }
}

void Anya(int C[]) {
    for (int i = 1; i < n; ++i) {
        Save(i + n, pdis[B[i]] = C[i - 1]);
    }
    dfs2(1, 0, 0);
    for (int o = 0; o < int(D[0].size()); ++o) {
        int d = dist[D[0][o]];
        for (int i = 0; i < lg; ++i) {
            Save(o * lg + i, d & 1);
            d >>= 1;
        }
    }
}

Boris

#include <bits/stdc++.h>

using namespace std;

int Ask(int);

const static int mod = 12, lg = 9;
static int A[501], B[501], n;
static vector<int> edge[501];
static vector<int> D[mod];
static int par[501], pari[501];

void dfs1(int x, int p, int d) {
    par[x] = p;
    if (d) D[d % mod].push_back(x);
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs1(i, x, d + 1);
    }
}

static int ord[501];
void InitBoris(int _n, int _A[], int _B[]) {
    n = _n;
    for (int i = 1; i < n; ++i) {
        A[i] = _A[i - 1] + 1;
        B[i] = _B[i - 1] + 1;
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    dfs1(1, 0, 0);
    for (int i = 1; i < n; ++i) {
        if (par[A[i]] == B[i]) swap(A[i], B[i]);
        pari[B[i]] = i;
    }
    int mn = 0;
    for (int i = 1; i < mod; ++i) if (D[i].size() < D[mn].size()) mn = i;
    swap(D[0], D[mn]);
    memset(ord, -1, sizeof(ord));
    for (int i = 0; i < int(D[0].size()); ++i) {
        ord[D[0][i]] = i;
    }
}

int Boris(int x) {
    ++x;
    int ret = 0;
    while (x > 1) {
        int o = ord[x];
        if (o < 0) {
            ret += Ask(pari[x] + n);
            x = par[x];
            continue;
        }
        int v = 0;
        for (int i = lg; i--; ) {
            v <<= 1;
            v |= Ask(o * lg + i);
        }
        return ret + v;
    }
    return ret;
}

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45