oj.uz

Submission #426499

# Submission time Handle Problem Language Result Execution time Memory
426499 2021-06-14T05:34:34 Z 장태환(#7571) City (JOI17_city) C++14
100 / 100
 653 ms 42868 KB 
#include "Encoder.h"
#include <vector>
using namespace std;
static vector<int>h;
static vector<int>link[250100];
static void init()
{
    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:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     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 6400 KB Output is correct
3 Correct 5 ms 6376 KB Output is correct
4 Correct 4 ms 6400 KB Output is correct
5 Correct 5 ms 6400 KB Output is correct
6 Correct 5 ms 6408 KB Output is correct
7 Correct 5 ms 6400 KB Output is correct
8 Correct 7 ms 6400 KB Output is correct
9 Correct 7 ms 6468 KB Output is correct
10 Correct 5 ms 6400 KB Output is correct
11 Correct 5 ms 6376 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 198 ms 17256 KB Output is correct - L = 116156
2 Correct 227 ms 17056 KB Output is correct - L = 129078
3 Correct 196 ms 17264 KB Output is correct - L = 110760
4 Correct 213 ms 17184 KB Output is correct - L = 118996
5 Correct 608 ms 42868 KB Output is correct - L = 54840400
6 Correct 558 ms 40280 KB Output is correct - L = 54138210
7 Correct 653 ms 40380 KB Output is correct - L = 52210560
8 Correct 608 ms 40180 KB Output is correct - L = 74619438
9 Correct 435 ms 40960 KB Output is correct - L = 159696466
10 Correct 514 ms 40960 KB Output is correct - L = 144439560
11 Correct 461 ms 40992 KB Output is correct - L = 174744206
12 Correct 480 ms 41048 KB Output is correct - L = 144417692
13 Correct 506 ms 40864 KB Output is correct - L = 100695324
14 Correct 571 ms 40492 KB Output is correct - L = 66379178
15 Correct 188 ms 16308 KB Output is correct - L = 119564
16 Correct 203 ms 16184 KB Output is correct - L = 112180
17 Correct 218 ms 16348 KB Output is correct - L = 110476
18 Correct 569 ms 40588 KB Output is correct - L = 158858666
19 Correct 569 ms 40424 KB Output is correct - L = 35499858
20 Correct 476 ms 40532 KB Output is correct - L = 35499858
21 Correct 539 ms 40484 KB Output is correct - L = 144417550
22 Correct 548 ms 40324 KB Output is correct - L = 35739412
23 Correct 588 ms 40432 KB Output is correct - L = 35835262
24 Correct 530 ms 40336 KB Output is correct - L = 37215360
25 Correct 544 ms 40348 KB Output is correct - L = 36266516
26 Correct 583 ms 40312 KB Output is correct - L = 39226932
27 Correct 558 ms 40304 KB Output is correct - L = 39503690