oj.uz

Submission #427285

# Submission time Handle Problem Language Result Execution time Memory
427285 2021-06-14T13:55:46 Z jjang36524 City (JOI17_city) C++14
100 / 100
 672 ms 53348 KB 
#include "Encoder.h"
#include "Device.h"

#include <vector>
using namespace std;
static vector<int>h;
static vector<int>link[250100];
static void init()
{
    h.clear();
    int s=1;
    int tl=21;
    h.push_back(s);
    while(tl)
    {
        s=max((double)s+1,s*1.1);
        h.push_back(s);
        if(s>=250000)
            tl--;
    }
}
static int l[250100],r[250100],c,s[250100];
static void dfs(int n,int p)
{
    l[n]=c++;
    int i;
    for(i=0;i<link[n].size();i++)
    {
        if(link[n][i]!=p)
        {
            dfs(link[n][i],n);
        }
    }
    r[n]=c=(*lower_bound(h.begin(),h.end(),c-l[n]))+l[n];
    s[n]=lower_bound(h.begin(),h.end(),c-l[n])-h.begin();
}
void Encode(int N, int A[], int B[])
{
    init();
	for (int i = 1; i < N; ++i)
	{
		link[A[i-1]].push_back(B[i-1]);
		link[B[i-1]].push_back(A[i-1]);
	}
	dfs(0,-1);
	for(int i=0;i<N;i++)
	{
        Code(i,l[i]*h.size()+s[i]);
	}
}
#include "Device.h"
#include <vector>
using namespace std;
static vector<int>h;
static void initt()
{
    int s=1;
    int tl=21;
    h.push_back(s);
    while(tl)
    {
        s=max((double)s+1,s*1.1);
        h.push_back(s);
        if(s>=250000)
            tl--;
    }
}
void InitDevice()
{
    initt();
}

int Answer(long long S, long long T)
{
    int sf=S/h.size();
    int tf=T/h.size();
    int se=h[S%h.size()]+sf;
    int te=h[T%h.size()]+tf;
    if(sf<=tf&&te<=se)
        return 1;
    if(tf<=sf&&se<=te)
    return 0;
    return 2;
}

Compilation message

Encoder.cpp: In function 'void dfs(int, int)':
Encoder.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(i=0;i<link[n].size();i++)
      |             ~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6400 KB Output is correct
2 Correct 5 ms 6396 KB Output is correct
3 Correct 4 ms 6476 KB Output is correct
4 Correct 4 ms 6488 KB Output is correct
5 Correct 5 ms 6376 KB Output is correct
6 Correct 5 ms 6464 KB Output is correct
7 Correct 7 ms 6488 KB Output is correct
8 Correct 5 ms 6484 KB Output is correct
9 Correct 6 ms 6432 KB Output is correct
10 Correct 7 ms 6400 KB Output is correct
11 Correct 5 ms 6404 KB Output is correct
12 Correct 5 ms 6400 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 21148 KB Output is correct - L = 116156
2 Correct 205 ms 21144 KB Output is correct - L = 129078
3 Correct 229 ms 21196 KB Output is correct - L = 110760
4 Correct 203 ms 21256 KB Output is correct - L = 118996
5 Correct 647 ms 50496 KB Output is correct - L = 54840400
6 Correct 661 ms 52424 KB Output is correct - L = 54138210
7 Correct 657 ms 52364 KB Output is correct - L = 52210560
8 Correct 633 ms 52100 KB Output is correct - L = 74619438
9 Correct 495 ms 53272 KB Output is correct - L = 159696466
10 Correct 511 ms 53324 KB Output is correct - L = 144439560
11 Correct 516 ms 53264 KB Output is correct - L = 174744206
12 Correct 546 ms 53348 KB Output is correct - L = 144417692
13 Correct 550 ms 52916 KB Output is correct - L = 100695324
14 Correct 570 ms 52588 KB Output is correct - L = 66379178
15 Correct 213 ms 21844 KB Output is correct - L = 119564
16 Correct 226 ms 21884 KB Output is correct - L = 112180
17 Correct 216 ms 21944 KB Output is correct - L = 110476
18 Correct 558 ms 52488 KB Output is correct - L = 158858666
19 Correct 672 ms 52516 KB Output is correct - L = 35499858
20 Correct 613 ms 52560 KB Output is correct - L = 35499858
21 Correct 535 ms 52640 KB Output is correct - L = 144417550
22 Correct 541 ms 52648 KB Output is correct - L = 35739412
23 Correct 546 ms 52684 KB Output is correct - L = 35835262
24 Correct 594 ms 52612 KB Output is correct - L = 37215360
25 Correct 528 ms 52488 KB Output is correct - L = 36266516
26 Correct 573 ms 52512 KB Output is correct - L = 39226932
27 Correct 543 ms 52576 KB Output is correct - L = 39503690