Submission #1009178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009178		hmm789	City (JOI17_city)	C++14	8 / 100	226 ms	55968 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
#define int long long
int idx, code[500000];
vector<int> adj[500000];
 
void solve(vector<int> &v, int p, int l, int r) {
    if(l > r) return;
    if(l == r) {
        code[v[l]] = 2*code[p];
    } else if(r-l == 1) {
        code[v[l]] = 2*code[p];
        code[v[r]] = 2*code[p]+1;
    } else {
        int m = (l+r)/2;
        code[++idx] = 2*code[p];
        solve(v, idx, l, m);
        code[++idx] = 2*code[p]+1;
        solve(v, idx, m+1, r);
    }
}
 
void dfs(int x, int p) {
    vector<int> v;
    for(int i : adj[x]) if(i != p) v.push_back(i);
    solve(v, x, 0, v.size()-1);
    for(int i : adj[x]) if(i != p) dfs(i, x);
}
 
#undef int
void Encode(int N, int A[], int B[]) {
#define int long long
    for(int i = 0; i < N-1; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    code[0] = 1;
    idx = N-1;
    dfs(0, -1);
    for(int i = 0; i < N; i++) Code(i, code[i]);
#undef int
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
 
void InitDevice() {
}
 
int Answer(long long S, long long T) {
#define int long long
    int ss = 64-__builtin_clzll(S);
    int st = 64-__builtin_clzll(T);
    if(ss == st) {
        return 2;
    } else if(ss > st) {
        S >>= (ss-st);
        if(S == T) return 0;
        else return 2;
    } else {
        T >>= (st-ss);
        if(S == T) return 1;
        else return 2;
    }
#undef int
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92