Submission #1009435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009435		hmm789	City (JOI17_city)	C++14	100 / 100	250 ms	53444 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);
    int sz = cur-pre[x]+1;
    len[x] = lower_bound(pw, pw+300, sz)-pw;
    cur += pw[len[x]] - sz;
}
 
#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;
#define int long long 
 
int pw[300];
const double r = 1.05;
 
void InitDevice() {
	double num = 1;
    pw[0] = 1;
    for(int i = 1; i < 300; i++) {
        num *= r;
        pw[i] = (int)ceil(num);
    }
}
 
#undef int
int Answer(long long S, long long T) {
#define int long long
    int pres = S/300, posts = pres+pw[S%300]-1;
    int pret = T/300, postt = pret+pw[T%300]-1;
    if(pres < pret && posts >= postt) return 1;
    if(pret < pres && postt >= posts) return 0;
    return 2;
#undef int
}

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