oj.uz

Submission #412185

# Submission time Handle Problem Language Result Execution time Memory
412185 2021-05-26T15:19:51 Z AKaan37 Stations (IOI20_stations) C++17
21 / 100
 1097 ms 740 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 1005;
const lo mod = 1000000007;

int sayac=0,mx;
vector<int> vec[li],vv;
int dp[li];

inline void dfs1(int node,int ata,int der){
	mx=max(mx,der);
	for(auto go:vec[node]){
		if(go==ata)continue;
		dfs1(go,node,der+1);
	}
}

inline void dfs(int node,int ata){
	vv[node]=sayac++;
	int flagg=0;
	//~ vv[node]+=(1<<node);
	for(auto go:vec[node]){
		if(go==ata)continue;
		flagg=1;
		dfs(go,node);
		//~ vv[node]+=vv[go];
	}
	if(flagg==0)sayac+=1000;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> vvv) {
	std::vector<int> labels(n);
	sayac=0;
	for(int i=0;i<n;i++)vec[i].clear();
	for(int i=0;i<n-1;i++){
		vec[u[i]].pb(vvv[i]);
		vec[vvv[i]].pb(u[i]);
	}
	vv.clear();
	int ind=-1;
	for(int i=0;i<n;i++){
		vv.pb(0);
		if((int)vec[i].size()>2)ind=i;
	}
	if(ind==-1){
		for(int i=0;i<n;i++){
			if((int)vec[i].size()==1)ind=i;
		}
	}
	//~ cout<<ind
	dfs1(ind,-1,0);
	//~ mx=max(mx,1000-1);
	dfs(ind,-1);
	for (int i = 0; i < n; i++) {
		//~ cout<<vv[i]<<" ** "<<endl;
		labels[i] = vv[i];
	}
	return labels;
}

inline int f(int sira,int hedef){
	int cevv=0;
	if(sira>hedef)return 0;
	if(sira==hedef)return 1;
	if(~dp[sira])return dp[sira];
	cevv=max(cevv,f(sira*2+1,hedef));
	cevv=max(cevv,f(sira*2+2,hedef));
	return dp[sira]=cevv;
}

int find_next_station(int s, int t, std::vector<int> c) {
	//~ for(int i=0;i<(int)c.size()-1;i++){
		//~ if((c[i]&t)==t)return c[i];
	//~ }
	//~ return c[(int)c.size()-1];
	if(t==0)return c[0];
	if((int)c.size()==1)return c[0];
	if(t<s)return c[0];
	if(abs(t-s)>=1000 && (int)c.size()==2)return c[0];
	if((int)c.size()==2)return c[1];
	int siz=(int)c.size();
	for(int i=0;i<siz-1;i++){
		if(c[i+1]>t)return c[i];
	}
	return c[siz-1];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 528 KB Output is correct
2 Correct 591 ms 504 KB Output is correct
3 Correct 1097 ms 500 KB Output is correct
4 Correct 822 ms 400 KB Output is correct
5 Correct 782 ms 400 KB Output is correct
6 Correct 572 ms 528 KB Output is correct
7 Correct 500 ms 504 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 2 ms 480 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 308 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=4, label=128265
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 516 KB Output is correct
2 Correct 576 ms 516 KB Output is correct
3 Correct 1009 ms 400 KB Output is correct
4 Correct 839 ms 544 KB Output is correct
5 Correct 633 ms 512 KB Output is correct
6 Correct 429 ms 520 KB Output is correct
7 Correct 537 ms 528 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 764 ms 400 KB Output is correct
12 Correct 609 ms 648 KB Output is correct
13 Correct 541 ms 620 KB Output is correct
14 Correct 442 ms 512 KB Output is correct
15 Correct 52 ms 460 KB Output is correct
16 Correct 85 ms 556 KB Output is correct
17 Correct 162 ms 740 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 696 KB Output is correct
2 Correct 854 ms 400 KB Output is correct
3 Correct 763 ms 400 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 628 ms 520 KB Output is correct
8 Correct 1051 ms 400 KB Output is correct
9 Correct 715 ms 400 KB Output is correct
10 Correct 701 ms 528 KB Output is correct
11 Incorrect 5 ms 468 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 644 KB Output is correct
2 Correct 612 ms 516 KB Output is correct
3 Correct 933 ms 400 KB Output is correct
4 Correct 772 ms 400 KB Output is correct
5 Correct 632 ms 528 KB Output is correct
6 Correct 543 ms 516 KB Output is correct
7 Correct 531 ms 528 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Incorrect 543 ms 528 KB Wrong query response.
12 Halted 0 ms 0 KB -