oj.uz

Submission #430329

# Submission time Handle Problem Language Result Execution time Memory
430329 2021-06-16T12:58:55 Z dreezy Stations (IOI20_stations) C++17
54.8751 / 100
 1402 ms 816 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

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

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 28 ms 320 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=2050
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 640 KB Output is correct
2 Correct 715 ms 668 KB Output is correct
3 Correct 1236 ms 400 KB Output is correct
4 Correct 722 ms 400 KB Output is correct
5 Correct 696 ms 400 KB Output is correct
6 Correct 707 ms 612 KB Output is correct
7 Correct 622 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 6 ms 480 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 691 ms 520 KB Output is correct
12 Correct 661 ms 644 KB Output is correct
13 Correct 599 ms 816 KB Output is correct
14 Correct 571 ms 528 KB Output is correct
15 Correct 73 ms 420 KB Output is correct
16 Correct 104 ms 504 KB Output is correct
17 Correct 144 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1154 ms 488 KB Output is correct
2 Correct 880 ms 472 KB Output is correct
3 Correct 843 ms 528 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 760 ms 404 KB Output is correct
8 Correct 1015 ms 400 KB Output is correct
9 Correct 835 ms 400 KB Output is correct
10 Correct 573 ms 400 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 4 ms 460 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 731 ms 400 KB Output is correct
17 Correct 656 ms 608 KB Output is correct
18 Correct 861 ms 400 KB Output is correct
19 Correct 686 ms 400 KB Output is correct
20 Correct 649 ms 484 KB Output is correct

Subtask #5
28.8751 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 647 ms 648 KB Partially correct
2 Partially correct 755 ms 692 KB Partially correct
3 Correct 1402 ms 400 KB Output is correct
4 Partially correct 884 ms 400 KB Partially correct
5 Partially correct 916 ms 400 KB Partially correct
6 Partially correct 709 ms 656 KB Partially correct
7 Partially correct 720 ms 528 KB Partially correct
8 Partially correct 3 ms 468 KB Partially correct
9 Partially correct 5 ms 468 KB Partially correct
10 Partially correct 2 ms 420 KB Partially correct
11 Partially correct 481 ms 616 KB Partially correct
12 Partially correct 679 ms 528 KB Partially correct
13 Correct 1160 ms 520 KB Output is correct
14 Partially correct 805 ms 400 KB Partially correct
15 Partially correct 763 ms 492 KB Partially correct
16 Partially correct 577 ms 528 KB Partially correct
17 Partially correct 800 ms 400 KB Partially correct
18 Partially correct 554 ms 648 KB Partially correct
19 Partially correct 736 ms 688 KB Partially correct
20 Partially correct 535 ms 484 KB Partially correct
21 Partially correct 49 ms 400 KB Partially correct
22 Partially correct 129 ms 544 KB Partially correct
23 Partially correct 125 ms 624 KB Partially correct
24 Partially correct 4 ms 468 KB Partially correct
25 Partially correct 5 ms 432 KB Partially correct
26 Partially correct 6 ms 468 KB Partially correct
27 Partially correct 5 ms 472 KB Partially correct
28 Partially correct 2 ms 468 KB Partially correct
29 Partially correct 802 ms 400 KB Partially correct
30 Partially correct 640 ms 484 KB Partially correct
31 Partially correct 613 ms 528 KB Partially correct
32 Partially correct 619 ms 484 KB Partially correct
33 Partially correct 603 ms 484 KB Partially correct
34 Partially correct 358 ms 620 KB Partially correct
35 Partially correct 533 ms 528 KB Partially correct
36 Partially correct 518 ms 724 KB Partially correct
37 Partially correct 618 ms 604 KB Partially correct
38 Partially correct 461 ms 520 KB Partially correct
39 Partially correct 528 ms 636 KB Partially correct
40 Partially correct 510 ms 608 KB Partially correct
41 Partially correct 590 ms 728 KB Partially correct
42 Partially correct 87 ms 528 KB Partially correct
43 Partially correct 121 ms 528 KB Partially correct
44 Partially correct 198 ms 568 KB Partially correct
45 Partially correct 260 ms 596 KB Partially correct
46 Partially correct 366 ms 528 KB Partially correct
47 Partially correct 381 ms 736 KB Partially correct
48 Partially correct 94 ms 528 KB Partially correct
49 Partially correct 76 ms 612 KB Partially correct