oj.uz

Submission #114250

# Submission time Handle Problem Language Result Execution time Memory
114250 2019-05-31T14:55:51 Z faustaadp City (JOI17_city) C++17
22 / 100
 703 ms 116248 KB 
#include "Encoder.h"

#include <vector>
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll x[552525],ki[552525],ka[552525],sz,dep[552525],te;
vector<ll> v[552525];

void dfs(ll aa,ll bb)
{
	ll ii,sz=0;
	vector<ll> tem;
	priority_queue<pair<ll,ll> > pq;
	for(ii=0;ii<(ll)v[aa].size();ii++)
		if(v[aa][ii]!=bb)
		{
			dfs(v[aa][ii],aa);
			sz++;
			pq.push(mp(-dep[v[aa][ii]],v[aa][ii]));
		}
	while(sz>2)
	{
		ll xa=pq.top().se;
		pq.pop();
		ll xb=pq.top().se;
		pq.pop();
		te++;
		dep[te]=max(dep[xa],dep[xb])+1;
		ki[te]=xa;
		ka[te]=xb;
		pq.push(mp(-dep[te],te));
		sz--;
	}
	if(sz==2)
	{
		ll xa=pq.top().se;
		pq.pop();
		ll xb=pq.top().se;
		pq.pop();
		dep[aa]=max(dep[xa],dep[xb])+1;
		ki[aa]=xa;
		ka[aa]=xb;	
	}
	else
	if(sz==1)
	{
		ll xa=pq.top().se;
		pq.pop();
		dep[aa]=dep[xa]+1;
		ki[aa]=xa;
	}
	else
		dep[aa]=1;
}
void dfs2(ll aa,ll cc)
{
	if(aa==-1)return;
	x[aa]=cc;
	dfs2(ki[aa],cc*2+1);	
	dfs2(ka[aa],cc*2+2);	
}
void Encode(int N, int A[], int B[])
{
	int i;
 	for(i=0;i<(N-1);i++)
 	{
 		v[A[i]].pb(B[i]);
 		v[B[i]].pb(A[i]);
 	} 
 	te=N;
 	memset(ki,-1,sizeof(ki));
 	memset(ka,-1,sizeof(ka));
 	dfs(0,0);
 	dfs2(0,0);
 	for(i=0;i<N;i++)
 	{
 	//	cout<<i<<"->"<<x[i]<<"\n";
 		Code(i, x[i]);
 	}
}
#include "Device.h"

void InitDevice() {

}

int Answer(long long S, long long T) {
	if(S<T)
	{
		while(T>S)
		{
			T--;
			T/=2;	
		}
		if(T==S)return 1;
		return 2;
	}
	else
	{
		while(S>T)
		{
			S--;
			S/=2;
		}
		if(S==T)return 0;
  		return 2;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 44024 KB Output is correct
2 Correct 30 ms 44032 KB Output is correct
3 Correct 21 ms 44032 KB Output is correct
4 Correct 22 ms 44032 KB Output is correct
5 Correct 23 ms 44032 KB Output is correct
6 Correct 22 ms 44032 KB Output is correct
7 Correct 26 ms 43976 KB Output is correct
8 Correct 21 ms 44032 KB Output is correct
9 Correct 22 ms 44032 KB Output is correct
10 Correct 23 ms 44288 KB Output is correct
11 Correct 22 ms 44032 KB Output is correct
12 Correct 25 ms 44016 KB Output is correct

Subtask #2
14.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 58080 KB Output is correct - L = 16178
2 Correct 194 ms 57840 KB Output is correct - L = 130911
3 Correct 194 ms 57840 KB Output is correct - L = 16189
4 Correct 181 ms 58184 KB Output is correct - L = 1022
5 Correct 617 ms 108816 KB Output is correct - L = 134217469
6 Correct 647 ms 109040 KB Output is correct - L = 134217725
7 Correct 688 ms 108936 KB Output is correct - L = 134217725
8 Correct 703 ms 109552 KB Output is correct - L = 262142
9 Partially correct 624 ms 115240 KB Output is partially correct - L = 68719476734
10 Partially correct 624 ms 115816 KB Output is partially correct - L = 60129542142
11 Partially correct 632 ms 116000 KB Output is partially correct - L = 68685922302
12 Partially correct 622 ms 116248 KB Output is partially correct - L = 68291657726
13 Partially correct 622 ms 112896 KB Output is partially correct - L = 34359738366
14 Partially correct 640 ms 110832 KB Output is partially correct - L = 17179869182
15 Correct 177 ms 57840 KB Output is correct - L = 32765
16 Correct 186 ms 57856 KB Output is correct - L = 131065
17 Correct 196 ms 57840 KB Output is correct - L = 32759
18 Partially correct 616 ms 110168 KB Output is partially correct - L = 34153168893
19 Partially correct 629 ms 109664 KB Output is partially correct - L = 17181179901
20 Partially correct 620 ms 109856 KB Output is partially correct - L = 17180131325
21 Partially correct 625 ms 110728 KB Output is partially correct - L = 34359738365
22 Partially correct 626 ms 108952 KB Output is partially correct - L = 17180393467
23 Partially correct 669 ms 108840 KB Output is partially correct - L = 17180393467
24 Partially correct 659 ms 108136 KB Output is partially correct - L = 8590458875
25 Partially correct 614 ms 107320 KB Output is partially correct - L = 8590983163
26 Partially correct 662 ms 107024 KB Output is partially correct - L = 4296015867
27 Partially correct 611 ms 106680 KB Output is partially correct - L = 2149580795