oj.uz

Submission #383176

# Submission time Handle Problem Language Result Execution time Memory
383176 2021-03-29T06:02:42 Z kshitij_sodani City (JOI17_city) C++14
30 / 100
 554 ms 44516 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "Encoder.h"

vector<llo> adj[250001];
llo co=0;
llo st[250001];
llo endd[250001];
void dfs(llo no,llo par2=-1){
	st[no]=co;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no);
		}
	}
	co++;
	endd[no]=co-1;
}

void Encode(int n, int aa[], int bb[])
{

	for(int i=0;i<n-1;i++){
		adj[aa[i]].pb(bb[i]);
		adj[bb[i]].pb(aa[i]);
	}
	dfs(0);
	for (int i = 0; i < n; ++i) {
		Code(i, st[i]+((endd[i]*(endd[i]+1))/2));
	}




}

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

#include "Device.h"

void InitDevice()
{
}
llo val(llo x){
	return ((x*(x+1)))/2;
}
pair<llo,llo> cal(llo t){
	llo ind=-1;
	for(llo j=19;j>=0;j--){
		if(val(ind+(1LL<<j))<=t){
			//cout<<val(ind+(1LL<j))<<",,"<<t<<":"<<j<<endl;
			ind+=(1LL<<j);
		}
	}
	//cout<<t<<":"<<t-val(ind)<<":"<<ind<<endl;
	return {t-val(ind),ind};
}
int Answer(long long S, long long T)
{	llo xx2=250000;
	
	pair<llo,llo> xx=cal(S);
	pair<llo,llo> yy=cal(T);
	//0 if T is parent of S
	//1 if S is parent of T
	if(yy.a>=xx.a and yy.b<=xx.b){
		return 1;
	}
	if(yy.a<=xx.a and yy.b>=xx.b){
		return 0;
	}

	return 2;
}

Compilation message

Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:31:7: warning: unused variable 'xx2' [-Wunused-variable]
   31 | { llo xx2=250000;
      |       ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6852 KB Output is correct
2 Correct 6 ms 6628 KB Output is correct
3 Correct 6 ms 6756 KB Output is correct
4 Correct 7 ms 6852 KB Output is correct
5 Correct 6 ms 6756 KB Output is correct
6 Correct 6 ms 6628 KB Output is correct
7 Correct 6 ms 6860 KB Output is correct
8 Correct 7 ms 7276 KB Output is correct
9 Correct 6 ms 6628 KB Output is correct
10 Correct 6 ms 6872 KB Output is correct
11 Correct 6 ms 6756 KB Output is correct
12 Correct 6 ms 6860 KB Output is correct

Subtask #2
22.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 15600 KB Output is correct - L = 244650
2 Correct 262 ms 15432 KB Output is correct - L = 243951
3 Correct 228 ms 15556 KB Output is correct - L = 244650
4 Correct 227 ms 15760 KB Output is correct - L = 244650
5 Partially correct 544 ms 43196 KB Output is partially correct - L = 31249875000
6 Partially correct 543 ms 43244 KB Output is partially correct - L = 31249875000
7 Partially correct 536 ms 42824 KB Output is partially correct - L = 31249875000
8 Partially correct 550 ms 44516 KB Output is partially correct - L = 31249875000
9 Partially correct 474 ms 43416 KB Output is partially correct - L = 31249875000
10 Partially correct 443 ms 43508 KB Output is partially correct - L = 31249875000
11 Partially correct 441 ms 43572 KB Output is partially correct - L = 31249875000
12 Partially correct 469 ms 43376 KB Output is partially correct - L = 31249875000
13 Partially correct 506 ms 43156 KB Output is partially correct - L = 31249875000
14 Partially correct 518 ms 43076 KB Output is partially correct - L = 31249875000
15 Correct 235 ms 15596 KB Output is correct - L = 244650
16 Correct 234 ms 15636 KB Output is correct - L = 244650
17 Correct 224 ms 15808 KB Output is correct - L = 244650
18 Partially correct 507 ms 42716 KB Output is partially correct - L = 31249875000
19 Partially correct 492 ms 42612 KB Output is partially correct - L = 31249875000
20 Partially correct 527 ms 42652 KB Output is partially correct - L = 31249875000
21 Partially correct 503 ms 42968 KB Output is partially correct - L = 31249875000
22 Partially correct 510 ms 42360 KB Output is partially correct - L = 31249875000
23 Partially correct 510 ms 41992 KB Output is partially correct - L = 31249875000
24 Partially correct 524 ms 41784 KB Output is partially correct - L = 31249875000
25 Partially correct 523 ms 41708 KB Output is partially correct - L = 31249875000
26 Partially correct 554 ms 41940 KB Output is partially correct - L = 31249875000
27 Partially correct 536 ms 41516 KB Output is partially correct - L = 31249875000