Submission #1009418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009418		hmm789	City (JOI17_city)	C++14	0 / 100	117 ms	28896 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> adj[500000];
int pre[500000], len[500000], pw[300], cur;
const double r = 1.05;

void dfs(int x, int p) {
    pre[x] = cur++;
    for(int i : adj[x]) if(i != p) dfs(i, x);
    len[x] = lower_bound(pw, pw+260, cur-1-pre[x])-pw;
    cur = pre[x]+pw[len[x]]+1;
}

#undef int
void Encode(int N, int A[], int B[]) {
#define int long long
    double num = 1;
    pw[0] = 1;
    for(int i = 1; i < 300; i++) {
        num *= r;
        pw[i] = (int)ceil(num);
    }
    for(int i = 0; i < N-1; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    dfs(0, -1);
    for(int i = 0; i < N; i++) Code(i, len[i]+300*pre[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 pres = S/300, posts = pres+S%300;
    int pret = T/300, postt = pret+T%300;
    if(pres < pret && posts >= postt) return 1;
    if(pret < pres && postt >= posts) return 0;
    return 2;
#undef int
}

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