oj.uz

Submission #430307

# Submission time Handle Problem Language Result Execution time Memory
430307 2021-06-16T12:49:15 Z dreezy Stations (IOI20_stations) C++17
10 / 100
 1134 ms 656 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];
	}
}

int counter;
void name_subtree(int n, int p){
	labels[n] =sz[n] + (counter << shift) ;
	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();
	sz.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]);
	}
	
	int root = 0;		

	dfs1(0,-1);
	//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];
}


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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1134 ms 532 KB Output is correct
2 Correct 696 ms 484 KB Output is correct
3 Correct 776 ms 480 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 6 ms 476 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 697 ms 488 KB Output is correct
8 Correct 950 ms 400 KB Output is correct
9 Correct 803 ms 400 KB Output is correct
10 Correct 695 ms 400 KB Output is correct
11 Correct 8 ms 476 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 5 ms 476 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 645 ms 400 KB Output is correct
17 Correct 557 ms 656 KB Output is correct
18 Correct 623 ms 400 KB Output is correct
19 Correct 816 ms 496 KB Output is correct
20 Correct 604 ms 400 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 456 KB Invalid labels (duplicates values). scenario=7, label=999
2 Halted 0 ms 0 KB -