oj.uz

Submission #699314

# Submission time Handle Problem Language Result Execution time Memory
699314 2023-02-16T14:27:47 Z tengiz05 City (JOI17_city) C++17
100 / 100
 398 ms 32172 KB 
#include "Encoder.h"
#include <cmath>
#include <vector>
#include <algorithm>

constexpr int N = 700000;

// complementing subtree sizes and using much smaller numbers denoting the size

void Encode(int n, int A[], int B[]) {
    std::vector<int> f{1};
    int cur = 1;
    while (cur < N) {
        cur = std::ceil(cur * 1.05);
        f.push_back(cur);
    }
    std::vector<std::vector<int>> e(n);
    for (int i = 0; i < n - 1; i++) {
        e[A[i]].push_back(B[i]);
        e[B[i]].push_back(A[i]);
    }
	std::vector<int> in(n), siz(n);
    int timeStamp = 0;
    std::function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = timeStamp;
        siz[u] = 1;
        for (int v : e[u]) {
            if (v != p) {
                dfs(v, u);
                siz[u] += f[siz[v]];
            }
        }
        int orig = siz[u];
        siz[u] = std::lower_bound(f.begin(), f.end(), siz[u]) - f.begin();
        timeStamp += f[siz[u]] - orig + 1;
    };
    dfs(0, -1);
    for (int i = 0; i < n; i++) {
        Code(i, in[i] + siz[i] * 1LL * N);
    }
}

#include "Device.h"
#include <cmath>
#include <vector>

constexpr int N = 700000;
std::vector<int> f;

void InitDevice() {
    f = {1};
    int cur = 1;
    while (cur < N) {
        cur = std::ceil(cur * 1.05);
        f.push_back(cur);
    }
}

int Answer(long long S, long long T) {
	int ina = S % N;
    int outa = ina + f[S / N];
    int inb = T % N;
    int outb = inb + f[T / N];
    if (inb <= ina && outa <= outb) {
        return 0;
    } else if (ina <= inb && outb <= outa) {
        return 1;
    } else {
        return 2;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 524 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 0 ms 516 KB Output is correct
5 Correct 0 ms 516 KB Output is correct
6 Correct 0 ms 516 KB Output is correct
7 Correct 0 ms 516 KB Output is correct
8 Correct 0 ms 516 KB Output is correct
9 Correct 0 ms 516 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 516 KB Output is correct
12 Correct 0 ms 524 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 9172 KB Output is correct - L = 60200000
2 Correct 149 ms 8976 KB Output is correct - L = 60200000
3 Correct 153 ms 9192 KB Output is correct - L = 60200000
4 Correct 149 ms 9136 KB Output is correct - L = 60200000
5 Correct 393 ms 31424 KB Output is correct - L = 146300000
6 Correct 389 ms 31420 KB Output is correct - L = 146300000
7 Correct 393 ms 31332 KB Output is correct - L = 146300000
8 Correct 392 ms 31108 KB Output is correct - L = 148400000
9 Correct 344 ms 31992 KB Output is correct - L = 153300000
10 Correct 321 ms 32172 KB Output is correct - L = 154700000
11 Correct 331 ms 32052 KB Output is correct - L = 155400000
12 Correct 346 ms 32008 KB Output is correct - L = 155400000
13 Correct 365 ms 31804 KB Output is correct - L = 149800000
14 Correct 375 ms 31584 KB Output is correct - L = 147700000
15 Correct 153 ms 9060 KB Output is correct - L = 60900000
16 Correct 147 ms 9040 KB Output is correct - L = 60900000
17 Correct 152 ms 9232 KB Output is correct - L = 60200000
18 Correct 363 ms 31608 KB Output is correct - L = 154700000
19 Correct 380 ms 31620 KB Output is correct - L = 154700000
20 Correct 365 ms 31544 KB Output is correct - L = 154700000
21 Correct 398 ms 31760 KB Output is correct - L = 154000000
22 Correct 382 ms 31492 KB Output is correct - L = 154000000
23 Correct 379 ms 31488 KB Output is correct - L = 154000000
24 Correct 395 ms 31568 KB Output is correct - L = 153300000
25 Correct 380 ms 31524 KB Output is correct - L = 152600000
26 Correct 393 ms 31620 KB Output is correct - L = 151900000
27 Correct 384 ms 31432 KB Output is correct - L = 151200000