Submission #35058

#	Time	Username	Problem	Language	Result	Execution time	Memory
35058		Ushio	City (JOI17_city)	C++14	22 / 100	596 ms	72616 KiB

Encoder

#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);
}

Device

#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 / 8
• Subtask 2: 14 / 92