oj.uz

답안 #35058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35058 2017-11-17T20:40:21 Z Ushio City (JOI17_city) C++14
22 / 100
 596 ms 72616 KB 
#include "Encoder.h"

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 500005;
vector<int> G[kMaxN];
int Left[kMaxN], Right[kMaxN];
int nodes;
int n;

int DFS(int node, int par) {
    if (par != -1)
        G[node].erase(find(G[node].begin(), G[node].end(), par));

    priority_queue<pair<int, int>> Q;

    for (auto vec : G[node]) {
        int h = DFS(vec, node);
        Q.emplace(-h, vec);
    }

    while (Q.size() > 2) {
        auto a = Q.top(); Q.pop();
        auto b = Q.top(); Q.pop();

        ++nodes;
        Left[nodes] = a.second;
        Right[nodes] = b.second;
        Q.emplace(min(a.first, b.first) - 1, nodes);
    }

    if (Q.size() == 0) { Left[node] = Right[node] = -1; return 0; }
    if (Q.size() == 1) { Left[node] = Q.top().second; 
        Right[node] = -1; return 1 - Q.top().first; }
    if (Q.size() == 2) {
        auto a = Q.top(); Q.pop();
        auto b = Q.top(); Q.pop();

        Left[node] = a.second; 
        Right[node] = b.second;

        return 1 - min(a.first, b.first);
    }
    assert(false);
}

void CodeShit(int node, long long pref) {
    if (node == -1) return;
    if (node < n) {
        Code(node, pref);
    }
    CodeShit(Left[node], 2 * pref);
    CodeShit(Right[node], 2 * pref + 1);
}

void Encode(int n, int A[], int B[]) {
    ::n = n;
    for (int i = 0; i < n - 1; ++i) {
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }

    nodes = n;
    DFS(0, -1);
    CodeShit(0, 1LL);
}

#include "Device.h"

void InitDevice() {
}

bool ANC(long long anc, long long node) {
    while (node != anc) {
        if (node == 0) return false;
        node /= 2;
    }
    return true;
}

int Answer(long long S, long long T) {
    if (ANC(S, T)) return 1;
	if (ANC(T, S)) return 0;
    return 2;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24064 KB Output is correct
2 Correct 13 ms 24320 KB Output is correct
3 Correct 12 ms 24320 KB Output is correct
4 Correct 13 ms 24064 KB Output is correct
5 Correct 12 ms 24320 KB Output is correct
6 Correct 13 ms 24064 KB Output is correct
7 Correct 13 ms 24320 KB Output is correct
8 Correct 13 ms 24264 KB Output is correct
9 Correct 11 ms 24064 KB Output is correct
10 Correct 13 ms 24064 KB Output is correct
11 Correct 13 ms 24064 KB Output is correct
12 Correct 12 ms 24064 KB Output is correct

Subtask #2
14.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 31296 KB Output is correct - L = 16179
2 Correct 186 ms 31224 KB Output is correct - L = 130912
3 Correct 183 ms 31216 KB Output is correct - L = 16190
4 Correct 182 ms 31304 KB Output is correct - L = 1023
5 Correct 564 ms 67944 KB Output is correct - L = 134217470
6 Correct 572 ms 68240 KB Output is correct - L = 134217726
7 Correct 593 ms 68104 KB Output is correct - L = 134217726
8 Correct 591 ms 66464 KB Output is correct - L = 262143
9 Partially correct 573 ms 72096 KB Output is partially correct - L = 68719476735
10 Partially correct 574 ms 72608 KB Output is partially correct - L = 60129542143
11 Partially correct 559 ms 72520 KB Output is partially correct - L = 68685922303
12 Partially correct 534 ms 72616 KB Output is partially correct - L = 68291657727
13 Partially correct 552 ms 70624 KB Output is partially correct - L = 34359738367
14 Partially correct 539 ms 69576 KB Output is partially correct - L = 17179869183
15 Correct 185 ms 31216 KB Output is correct - L = 32766
16 Correct 184 ms 31216 KB Output is correct - L = 131066
17 Correct 186 ms 31104 KB Output is correct - L = 32760
18 Partially correct 567 ms 69512 KB Output is partially correct - L = 34153168894
19 Partially correct 578 ms 69888 KB Output is partially correct - L = 17181179902
20 Partially correct 571 ms 69776 KB Output is partially correct - L = 17180131326
21 Partially correct 578 ms 69504 KB Output is partially correct - L = 34359738366
22 Partially correct 578 ms 69208 KB Output is partially correct - L = 17180393468
23 Partially correct 577 ms 69104 KB Output is partially correct - L = 17180393468
24 Partially correct 571 ms 68560 KB Output is partially correct - L = 8590458876
25 Partially correct 589 ms 69064 KB Output is partially correct - L = 8590983164
26 Partially correct 596 ms 68440 KB Output is partially correct - L = 4296015868
27 Partially correct 583 ms 68008 KB Output is partially correct - L = 2149580796