oj.uz

Submission #60953

# Submission time Handle Problem Language Result Execution time Memory
60953 2018-07-25T04:13:31 Z 정원준(#1763) City (JOI17_city) C++11
22 / 100
 523 ms 60808 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 7 ms 12544 KB Output is correct
3 Correct 8 ms 12544 KB Output is correct
4 Correct 7 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 12536 KB Output is correct
8 Correct 8 ms 12544 KB Output is correct
9 Correct 8 ms 12544 KB Output is correct
10 Correct 9 ms 12544 KB Output is correct
11 Correct 9 ms 12544 KB Output is correct
12 Correct 8 ms 12544 KB Output is correct

Subtask #2
14.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 19440 KB Output is correct - L = 174757689
2 Correct 167 ms 19544 KB Output is correct - L = 174507678
3 Correct 170 ms 19480 KB Output is correct - L = 174757689
4 Correct 166 ms 19384 KB Output is correct - L = 174757689
5 Partially correct 504 ms 59096 KB Output is partially correct - L = 62502499989
6 Partially correct 454 ms 59248 KB Output is partially correct - L = 62502499989
7 Partially correct 513 ms 59032 KB Output is partially correct - L = 62502499989
8 Partially correct 501 ms 58584 KB Output is partially correct - L = 62502499989
9 Partially correct 420 ms 60320 KB Output is partially correct - L = 62502499989
10 Partially correct 411 ms 60696 KB Output is partially correct - L = 62502499989
11 Partially correct 419 ms 60736 KB Output is partially correct - L = 62502499989
12 Partially correct 414 ms 60808 KB Output is partially correct - L = 62502499989
13 Partially correct 443 ms 59872 KB Output is partially correct - L = 62502499989
14 Partially correct 478 ms 59472 KB Output is partially correct - L = 62502499989
15 Correct 166 ms 19552 KB Output is correct - L = 174757689
16 Correct 165 ms 19384 KB Output is correct - L = 174757689
17 Correct 168 ms 19384 KB Output is correct - L = 174757689
18 Partially correct 479 ms 59400 KB Output is partially correct - L = 62502499989
19 Partially correct 464 ms 59616 KB Output is partially correct - L = 62502499989
20 Partially correct 456 ms 59608 KB Output is partially correct - L = 62502499989
21 Partially correct 477 ms 59560 KB Output is partially correct - L = 62502499989
22 Partially correct 484 ms 59552 KB Output is partially correct - L = 62502499989
23 Partially correct 503 ms 59352 KB Output is partially correct - L = 62502499989
24 Partially correct 470 ms 59416 KB Output is partially correct - L = 62502499989
25 Partially correct 517 ms 59304 KB Output is partially correct - L = 62502499989
26 Partially correct 523 ms 59424 KB Output is partially correct - L = 62502499989
27 Partially correct 519 ms 58976 KB Output is partially correct - L = 62502499989