oj.uz

답안 #49471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49471 2018-05-29T10:15:03 Z SpaimaCarpatilor City (JOI17_city) C++17
100 / 100
 542 ms 64280 KB 
#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;

const int maxN = 250000, K = 252, maxM = 1000000;
int nr = 0, l[250009], length[250009], a[50009], firstAfter[maxM];
long long partialS[250009];
vector < int > v[250009];

void initA ()
{
    a[1] = 1;
    for (int i=2; i<=K; i++)
    {
        a[i] = (int) ((double) a[i - 1] * 1.05);
        if (a[i] <= a[i - 1]) a[i] = a[i - 1] + 1;
    }
    int j = 1;
    for (int i=1; i<=a[K]; i++)
    {
        while (a[j] < i)
            j ++;
        firstAfter[i] = j;
    }
}

void dfs (int nod, int tata)
{
    l[nod] = ++nr;
    for (auto it : v[nod])
        if (it != tata)
            dfs (it, nod);
    int L = firstAfter[nr - l[nod] + 1];
    nr = l[nod] + a[L] - 1;
    length[nod] = L;
}

void Encode (int N, int A[], int B[])
{
    for (int i=0; i<N - 1; i++)
        v[A[i]].push_back (B[i]),
        v[B[i]].push_back (A[i]);
    initA ();
    dfs (0, -1);
	for (int i=0; i<N; i++)
		Code(i, 1LL * length[i] * maxM + l[i]);
}

#include "Device.h"
#include<bits/stdc++.h>
using namespace std;

const int maxN = 250000, K = 252, maxM = 1000000;
static int a[50009];

void InitDevice()
{
    a[1] = 1;
    for (int i=2; i<=K; i++)
    {
        a[i] = (int) ((double) a[i - 1] * 1.05);
        if (a[i] <= a[i - 1]) a[i] = a[i - 1] + 1;
    }
}

void decode (long long X, int &i, int &j)
{
    j = X / maxM, i = X % maxM;
    j = a[j] + i - 1;
}

int Answer (long long S, long long T)
{
    int lS, rS; decode (S, lS, rS);
    int lT, rT; decode (T, lT, rT);
    if (lT <= lS && rS <= rT) return 0;
    if (lS <= lT && rT <= rS) return 1;
	return 2;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19968 KB Output is correct
2 Correct 12 ms 20224 KB Output is correct
3 Correct 12 ms 20096 KB Output is correct
4 Correct 12 ms 19968 KB Output is correct
5 Correct 11 ms 19968 KB Output is correct
6 Correct 12 ms 19968 KB Output is correct
7 Correct 11 ms 20168 KB Output is correct
8 Correct 12 ms 20008 KB Output is correct
9 Correct 11 ms 20064 KB Output is correct
10 Correct 12 ms 20168 KB Output is correct
11 Correct 12 ms 19968 KB Output is correct
12 Correct 12 ms 20224 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 27120 KB Output is correct - L = 105000001
2 Correct 180 ms 27200 KB Output is correct - L = 106000001
3 Correct 170 ms 27320 KB Output is correct - L = 104000001
4 Correct 172 ms 27120 KB Output is correct - L = 105000001
5 Correct 478 ms 62872 KB Output is correct - L = 228000001
6 Correct 511 ms 62968 KB Output is correct - L = 229000001
7 Correct 480 ms 62960 KB Output is correct - L = 229000001
8 Correct 491 ms 62192 KB Output is correct - L = 231000001
9 Correct 418 ms 64216 KB Output is correct - L = 239000001
10 Correct 399 ms 64208 KB Output is correct - L = 241000001
11 Correct 395 ms 64208 KB Output is correct - L = 242000001
12 Correct 421 ms 64280 KB Output is correct - L = 242000001
13 Correct 463 ms 63712 KB Output is correct - L = 234000001
14 Correct 475 ms 63152 KB Output is correct - L = 231000001
15 Correct 170 ms 27008 KB Output is correct - L = 105000001
16 Correct 172 ms 27264 KB Output is correct - L = 105000001
17 Correct 173 ms 27032 KB Output is correct - L = 105000001
18 Correct 474 ms 63328 KB Output is correct - L = 241000001
19 Correct 474 ms 63384 KB Output is correct - L = 241000001
20 Correct 454 ms 63400 KB Output is correct - L = 241000001
21 Correct 447 ms 63344 KB Output is correct - L = 240000001
22 Correct 542 ms 63176 KB Output is correct - L = 240000001
23 Correct 507 ms 63144 KB Output is correct - L = 240000001
24 Correct 487 ms 63216 KB Output is correct - L = 239000001
25 Correct 510 ms 63176 KB Output is correct - L = 238000001
26 Correct 508 ms 62960 KB Output is correct - L = 237000001
27 Correct 501 ms 62840 KB Output is correct - L = 236000001