oj.uz

Submission #411764

# Submission time Handle Problem Language Result Execution time Memory
411764 2021-05-25T20:47:35 Z AKaan37 Stations (IOI20_stations) C++17
10 / 100
 997 ms 636 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;
vector<int> vec[li],vv;
int dp[li];

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+=1001;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> vvv) {
	std::vector<int> labels(n);
	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;
		}
	}
	dfs(0,-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((int)c.size()==1)return c[0];
	if(abs(t-s)>=1001 && (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
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 412 KB Invalid labels (values out of range). scenario=1, k=1000000, vertex=1, label=93474275
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 520 KB Output is correct
2 Correct 823 ms 636 KB Output is correct
3 Correct 818 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 775 ms 528 KB Output is correct
8 Correct 946 ms 400 KB Output is correct
9 Correct 813 ms 512 KB Output is correct
10 Correct 757 ms 516 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 5 ms 432 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 2 ms 476 KB Output is correct
16 Correct 639 ms 552 KB Output is correct
17 Correct 635 ms 528 KB Output is correct
18 Correct 505 ms 512 KB Output is correct
19 Correct 623 ms 400 KB Output is correct
20 Correct 616 ms 424 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 328 KB Invalid labels (values out of range). scenario=1, k=1000000000, vertex=1, label=1749293001
2 Halted 0 ms 0 KB -