oj.uz

답안 #257325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257325 2020-08-04T06:02:08 Z imeimi2000 Snowy Roads (JOI16_snowy) C++17
0 / 100
 12 ms 1472 KB 
#include <bits/stdc++.h>

using namespace std;

void Save(int, int);

const static int mod = 11, 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);
    }
}

static int ord[501];
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]);
    memset(ord, -1, sizeof(ord));
    for (int i = 0; i < int(D[0].size()); ++i) {
        ord[D[0][i]] = i;
    }
}

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 x : D[0]) {
        int o = ord[x], d = dist[x];
        for (int i = 0; i < lg; ++i) {
            Save(o * lg + i, d & 1);
            d >>= 1;
        }
    }
}
#include <bits/stdc++.h>

using namespace std;

int Ask(int);

const static int mod = 11, lg = 9;
static int A[501], B[501], n;
static vector<int> edge[501];
static vector<int> D[501];
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 = 0; i < lg; ++i) {
            v <<= 1;
            v |= Ask(o * lg + i);
        }
        ret += v;
    }
    return ret;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 996 KB Output is correct
2 Correct 2 ms 788 KB Output is correct
3 Correct 4 ms 972 KB Output is correct
4 Incorrect 2 ms 1120 KB Wrong Answer [6]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1436 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 1320 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 1472 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -