oj.uz

답안 #99344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99344 2019-03-02T19:40:09 Z TadijaSebez City (JOI17_city) C++11
100 / 100
 399 ms 35336 KB 
#include "Encoder.h"
#define ll long long
const int N=250050*2;
const int M=2*N;
int fir[N],go[M],tot,f[M];
void Add(int u, int v){ tot++;f[tot]=v;go[tot]=fir[u];fir[u]=tot;}
void AddEdge(int u, int v){ Add(u,v);Add(v,u);}
int lid[N],rid[N],tid;
void DFS(int u, int p)
{
	lid[u]=tid++;
	for(int i=fir[u];i;i=go[i]) if(f[i]!=p) DFS(f[i],u);
	double cur=1.0,w=1.05;
	int ans=0;
	while((int)cur<tid-lid[u]) cur*=w,ans++;
	tid=lid[u]+(int)cur;
	Code(u,(ll)ans*N+lid[u]);
}
void Encode(int n, int a[], int b[])
{
	for(int i=0;i<n-1;i++) AddEdge(a[i],b[i]);
	DFS(0,-1);
}
#include "Device.h"
const int N=250050*2;
double ans[2050];
void InitDevice()
{
	ans[0]=1.0;
	for(int i=1;i<2050;i++) ans[i]=ans[i-1]*1.05;
}

int Answer(long long S, long long T)
{
	int x=S/N,l=S%N,r=l+(int)ans[x]-1;
	int y=T/N,L=T%N,R=L+(int)ans[y]-1;
	if(l<=L && R<=r) return 1;
	if(L<=l && r<=R) return 0;
	return 2;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 744 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 776 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 904 KB Output is correct
11 Correct 4 ms 896 KB Output is correct
12 Correct 3 ms 768 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 9280 KB Output is correct - L = 68013600
2 Correct 161 ms 9192 KB Output is correct - L = 68513700
3 Correct 163 ms 9216 KB Output is correct - L = 68013600
4 Correct 161 ms 9236 KB Output is correct - L = 68513700
5 Correct 399 ms 35144 KB Output is correct - L = 129525900
6 Correct 359 ms 35016 KB Output is correct - L = 130026000
7 Correct 373 ms 35248 KB Output is correct - L = 130026000
8 Correct 364 ms 35056 KB Output is correct - L = 131526300
9 Correct 338 ms 35312 KB Output is correct - L = 135027000
10 Correct 345 ms 35240 KB Output is correct - L = 136027200
11 Correct 355 ms 35216 KB Output is correct - L = 136027200
12 Correct 331 ms 35048 KB Output is correct - L = 136027200
13 Correct 365 ms 35056 KB Output is correct - L = 132526500
14 Correct 392 ms 35080 KB Output is correct - L = 130526100
15 Correct 168 ms 9328 KB Output is correct - L = 68013600
16 Correct 166 ms 9256 KB Output is correct - L = 68013600
17 Correct 159 ms 9316 KB Output is correct - L = 68013600
18 Correct 351 ms 35104 KB Output is correct - L = 135527100
19 Correct 374 ms 35184 KB Output is correct - L = 135527100
20 Correct 352 ms 35144 KB Output is correct - L = 135527100
21 Correct 357 ms 35312 KB Output is correct - L = 135027000
22 Correct 360 ms 35104 KB Output is correct - L = 135527100
23 Correct 361 ms 35336 KB Output is correct - L = 135527100
24 Correct 373 ms 35000 KB Output is correct - L = 135027000
25 Correct 365 ms 35160 KB Output is correct - L = 134526900
26 Correct 390 ms 35192 KB Output is correct - L = 134026800
27 Correct 366 ms 35128 KB Output is correct - L = 133026600