oj.uz

답안 #363674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363674 2021-02-06T19:25:33 Z denkendoemeer City (JOI17_city) C++14
100 / 100
 494 ms 54164 KB 
#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>g[250005],r;
int in[250005],t[250005],u;
void dfs(int nod,int ta)
{
    in[nod]=u++;
    for(auto it:g[nod]){
        if (it!=ta)
            dfs(it,nod);
    }
    if (in[nod]==u-1)
        return ;
    int &ans=t[nod];
    while(in[nod]+r[ans]<u-1)
        ans++;
    u=in[nod]+r[ans]+1;
}
void Encode(int n,int a[],int b[])
{
    double d=1.050045;
    r.push_back(0);
    int i;
    for(i=1;i<256;i++){
        int aux=d*r.back();
        if (r.back()==aux)
            ++aux;
        r.push_back(aux);
    }
    for(i=0;i<n-1;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(0,-1);
    for(i=0;i<n;i++)
        Code(i,in[i]+(t[i]<<20));
}

#include "Device.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>aux;
void InitDevice()
{
    double d=1.050045;
    aux.push_back(0);
    int i;
    for(i=1;i<256;i++){
        int nr=aux.back()*d;
        if (aux.back()==nr)
            ++nr;
        aux.push_back(nr);
    }
}
int Answer(ll s,ll t)
{
    int aux1,aux2,aux3,aux4;
    aux1=s&((1<<20)-1);
    aux2=t&((1<<20)-1);
    aux3=aux1+aux[s>>20];
    aux4=aux2+aux[t>>20];
    if (aux2<=aux1 && aux3<=aux4)
        return 0;
    if (aux1<=aux2 && aux4<=aux3)
        return 1;
    return 2;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6852 KB Output is correct
2 Correct 4 ms 6760 KB Output is correct
3 Correct 4 ms 6632 KB Output is correct
4 Correct 5 ms 6860 KB Output is correct
5 Correct 4 ms 6860 KB Output is correct
6 Correct 4 ms 6760 KB Output is correct
7 Correct 4 ms 6860 KB Output is correct
8 Correct 4 ms 6760 KB Output is correct
9 Correct 4 ms 6852 KB Output is correct
10 Correct 6 ms 6860 KB Output is correct
11 Correct 5 ms 6852 KB Output is correct
12 Correct 4 ms 6860 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 22256 KB Output is correct - L = 110100480
2 Correct 196 ms 22312 KB Output is correct - L = 110100480
3 Correct 199 ms 22496 KB Output is correct - L = 109051904
4 Correct 198 ms 22300 KB Output is correct - L = 111149056
5 Correct 494 ms 52892 KB Output is correct - L = 239075328
6 Correct 476 ms 53060 KB Output is correct - L = 240123904
7 Correct 488 ms 53196 KB Output is correct - L = 240123904
8 Correct 479 ms 52720 KB Output is correct - L = 243269632
9 Correct 414 ms 54164 KB Output is correct - L = 250609664
10 Correct 406 ms 54004 KB Output is correct - L = 252706816
11 Correct 402 ms 53268 KB Output is correct - L = 252706816
12 Correct 397 ms 53052 KB Output is correct - L = 253755392
13 Correct 440 ms 53632 KB Output is correct - L = 245366784
14 Correct 459 ms 53020 KB Output is correct - L = 242221056
15 Correct 198 ms 22452 KB Output is correct - L = 110100480
16 Correct 196 ms 22348 KB Output is correct - L = 110100480
17 Correct 198 ms 22432 KB Output is correct - L = 110100480
18 Correct 440 ms 52820 KB Output is correct - L = 252706816
19 Correct 454 ms 53456 KB Output is correct - L = 252706816
20 Correct 441 ms 53172 KB Output is correct - L = 252706816
21 Correct 446 ms 52976 KB Output is correct - L = 251658240
22 Correct 460 ms 53308 KB Output is correct - L = 251658240
23 Correct 468 ms 53116 KB Output is correct - L = 251658240
24 Correct 469 ms 53420 KB Output is correct - L = 250609664
25 Correct 473 ms 52868 KB Output is correct - L = 249561088
26 Correct 489 ms 53360 KB Output is correct - L = 248512512
27 Correct 482 ms 52852 KB Output is correct - L = 247463936