oj.uz

Submission #430342

# Submission time Handle Problem Language Result Execution time Memory
430342 2021-06-16T13:02:48 Z dreezy Stations (IOI20_stations) C++17
10 / 100
 1230 ms 772 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
const int shift = 8;

vector<int> labels;
vector<vector<int>> graph;

vector<int> sz;
void dfs1(int n,int p){//calc sizes
	sz[n] = 1;
	for(int adj : graph[n])
	{
		if(adj == p) continue;
		dfs1(adj, n);
		sz[n] += sz[adj];
	}
}

vector<bool> vis;
int getcentroid(int n){
	dfs1(n, -1);
	vis[n] = true;
	
	for(int adj : graph[n]){
		if(!vis[adj] and sz[adj] >= sz.size()/2){
			//cout << adj<<": "<<sz[adj]<<endl;
			return getcentroid(adj);
		}
	}
	return n;
	
}

int counter;
void name_subtree(int n, int p){
	labels[n] =sz[n] + (counter << shift) ;
	if(p == -1) labels[n] = 0;
	counter++;
	for(int adj : graph[n]){
		if(adj == p)
		continue;
		name_subtree(adj, n);
	}
}


vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	counter = 0;
	sz.clear();
	labels.clear();
	graph.clear();
	vis.clear();
	sz.assign(n, 0);
	vis.assign(n, 0);
	labels.assign(n, 0);
	graph.assign( n, vector<int>());
	for (int i = 0; i < n - 1; i++) {
		graph[u[i]].pb(v[i]);
		graph[v[i]].pb(u[i]);
	}
	

	//dfs1(0,-1);
	int root = getcentroid(0);		
	//for(int i =0; i<n; i++) cout <<i<<": "<< sz[i]<<endl;
	
	name_subtree(root, -1);
	
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	
	int startind = ( s>> shift);
	int targetind = (t>>shift);
	for(int adj : c){
		int adjind = (adj >> shift);
		if(adjind < startind) continue;
		//cout << s <<"->"<<t<<": "<<adj<<", "<<sz[adj]<<endl;
		if(adjind<= targetind and targetind <= adjind + adj - (adjind<<shift) -1){
			//cout << startind<<"->"<<targetind<<": "<<adjind<<", "<<adj - (adjind<<10) -1 <<endl;
			return adj;
		}
	}
	return c[0];
}


/************/

Compilation message

stations.cpp: In function 'int getcentroid(int)':
stations.cpp:29:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   if(!vis[adj] and sz[adj] >= sz.size()/2){

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 772 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1190 ms 400 KB Output is correct
2 Correct 1051 ms 400 KB Output is correct
3 Correct 804 ms 492 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 917 ms 484 KB Output is correct
8 Correct 1230 ms 536 KB Output is correct
9 Correct 694 ms 488 KB Output is correct
10 Correct 871 ms 572 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 472 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 5 ms 552 KB Output is correct
15 Correct 2 ms 552 KB Output is correct
16 Correct 918 ms 488 KB Output is correct
17 Correct 684 ms 400 KB Output is correct
18 Correct 718 ms 572 KB Output is correct
19 Correct 755 ms 400 KB Output is correct
20 Correct 529 ms 528 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 676 ms 648 KB Wrong query response.
2 Halted 0 ms 0 KB -