oj.uz

Submission #60951

# Submission time Handle Problem Language Result Execution time Memory
60951 2018-07-25T04:10:41 Z 정원준(#1763) City (JOI17_city) C++11
22 / 100
 531 ms 60608 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
#define L long long

using namespace std;

void Code(int,long long);

int chk[250050];


vector<int>v[250050];
int order[250050],ordtop,lef[250050],rig[250050];


void dfs(int x){
	int i;
	order[x]=lef[x]=rig[x]=ordtop;
	ordtop++;
	for(i=0;i<v[x].size();i++)
	{
		if(!chk[v[x][i]])
		{
			chk[v[x][i]]=1;
			dfs(v[x][i]);
			lef[x]=min(lef[x],lef[v[x][i]]);
			rig[x]=max(rig[x],rig[v[x][i]]);
		}
	}
}



void Encode(int N,int A[],int B[]){
	int i;
	for(i=0;i<N-1;i++)
	{
		v[A[i]].push_back(B[i]);
		v[B[i]].push_back(A[i]);
	}
	chk[0]=1;
	dfs(0);
	for(i=0;i<N;i++)
	{
		Code(i,(L)lef[i]*(L)250010+(L)rig[i]);
	}
}

#include "Device.h"
#include <bits/stdc++.h>
#define L long long

using namespace std;

void InitDevice(){
	return;
}

int Answer(L S,L T){
	L lef1=S/250010,rig1=S%250010;
	L lef2=T/250010,rig2=T%250010;
	if(lef1<=lef2&&rig2<=rig1) return 1;
	if(lef2<=lef1&&rig1<=rig2) return 0;
	return 2;
}

Compilation message

Encoder.cpp: In function 'void dfs(int)':
Encoder.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12544 KB Output is correct
2 Correct 8 ms 12544 KB Output is correct
3 Correct 8 ms 12544 KB Output is correct
4 Correct 8 ms 12544 KB Output is correct
5 Correct 8 ms 12544 KB Output is correct
6 Correct 8 ms 12544 KB Output is correct
7 Correct 8 ms 12544 KB Output is correct
8 Correct 9 ms 12544 KB Output is correct
9 Correct 8 ms 12544 KB Output is correct
10 Correct 8 ms 12544 KB Output is correct
11 Correct 8 ms 12544 KB Output is correct
12 Correct 9 ms 12544 KB Output is correct

Subtask #2
14.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 19528 KB Output is correct - L = 174757689
2 Correct 172 ms 19480 KB Output is correct - L = 174507678
3 Correct 167 ms 19440 KB Output is correct - L = 174757689
4 Correct 174 ms 19440 KB Output is correct - L = 174757689
5 Partially correct 491 ms 59120 KB Output is partially correct - L = 62502499989
6 Partially correct 489 ms 59176 KB Output is partially correct - L = 62502499989
7 Partially correct 492 ms 59488 KB Output is partially correct - L = 62502499989
8 Partially correct 494 ms 58520 KB Output is partially correct - L = 62502499989
9 Partially correct 420 ms 60432 KB Output is partially correct - L = 62502499989
10 Partially correct 410 ms 60584 KB Output is partially correct - L = 62502499989
11 Partially correct 418 ms 60504 KB Output is partially correct - L = 62502499989
12 Partially correct 411 ms 60608 KB Output is partially correct - L = 62502499989
13 Partially correct 472 ms 59976 KB Output is partially correct - L = 62502499989
14 Partially correct 453 ms 59368 KB Output is partially correct - L = 62502499989
15 Correct 167 ms 19440 KB Output is correct - L = 174757689
16 Correct 172 ms 19384 KB Output is correct - L = 174757689
17 Correct 167 ms 19440 KB Output is correct - L = 174757689
18 Partially correct 470 ms 59704 KB Output is partially correct - L = 62502499989
19 Partially correct 504 ms 59536 KB Output is partially correct - L = 62502499989
20 Partially correct 472 ms 59552 KB Output is partially correct - L = 62502499989
21 Partially correct 466 ms 59480 KB Output is partially correct - L = 62502499989
22 Partially correct 506 ms 59440 KB Output is partially correct - L = 62502499989
23 Partially correct 490 ms 59664 KB Output is partially correct - L = 62502499989
24 Partially correct 512 ms 59176 KB Output is partially correct - L = 62502499989
25 Partially correct 497 ms 59216 KB Output is partially correct - L = 62502499989
26 Partially correct 531 ms 59168 KB Output is partially correct - L = 62502499989
27 Partially correct 521 ms 58976 KB Output is partially correct - L = 62502499989