oj.uz

Submission #392978

# Submission time Handle Problem Language Result Execution time Memory
392978 2021-04-22T13:21:16 Z REALITYNB Stations (IOI20_stations) C++14
10 / 100
 1037 ms 620 KB 
#include <bits/stdc++.h> 
#include "stations.h"
#define pii pair<int,int> 
#define in first 
#define out second
#define mp make_pair 
using namespace std; 

vector<int> label(int n ,int k , vector<int> u , vector<int> v){
	vector<int> ans(n) ; 
	vector<int> adj[n] ; 
	for(int i=0;i<n-1;i++) {
		adj[u[i]].push_back(v[i]) ; 
		adj[v[i]].push_back(u[i]) ; 
	}
	int tim = 0 ; 
	vector<int> inn(n) , outt(n) ; 
	function<void(int,int)> dfs = [&](int a, int p){
		inn[a]=tim++; 
		for(int x :adj[a]){
			if(x!=p){
				dfs(x,a) ; 
			}
		}
		outt[a]=++tim ; 
	}; 
	dfs(0,0) ; 
	for(int i=0;i<n;i++)
		ans[i]=inn[i]+((outt[i])<<10);
	return ans ; 
}
pii get(int x){
	return mp(x%(1<<10),(x>>10)) ; 
}
bool ancestor(pii s, pii b){
	return (s.in<=b.in&&b.out<=s.out); 
}
int find_next_station(int s ,int t, vector<int> ne){
	pii ss = get(s) , tt = get(t) ; 
	if(ancestor(ss,tt)^1){
		for(int x : ne){
			if(ancestor(get(x),ss)){
				return x ; 
			}
		}
	}
	for(int x : ne){
		if(ancestor(get(x),ss)^1 && ancestor(get(x),tt)){
			return x ; 
		}
	}
	if(s==t) return s ; 
	return 1 ; 
}
/*int main(){
	vector<int> u= {0,1,2} , v = {1,2,3} ;
	vector<int> res = label(4,1000000,u,v) ; 
	for(int x : res) cout << x <<" " ; 
	cout << endl ; 
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(i!=j){
				cout << i << " "<< j << ": " << find_next_station(i,j,adj[i]) << endl ; 
			}
		}
	}
	return 0 ; 
}*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 404 KB Output is correct
2 Correct 927 ms 496 KB Output is correct
3 Correct 651 ms 488 KB Output is correct
4 Correct 2 ms 472 KB Output is correct
5 Correct 5 ms 472 KB Output is correct
6 Correct 2 ms 400 KB Output is correct
7 Correct 664 ms 400 KB Output is correct
8 Correct 1031 ms 400 KB Output is correct
9 Correct 864 ms 404 KB Output is correct
10 Correct 701 ms 492 KB Output is correct
11 Correct 7 ms 472 KB Output is correct
12 Correct 4 ms 472 KB Output is correct
13 Correct 4 ms 476 KB Output is correct
14 Correct 4 ms 472 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 595 ms 400 KB Output is correct
17 Correct 607 ms 404 KB Output is correct
18 Correct 626 ms 400 KB Output is correct
19 Correct 492 ms 528 KB Output is correct
20 Correct 666 ms 400 KB Output is correct

Subtask #5
0 / 61.0

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