oj.uz

Submission #392985

# Submission time Handle Problem Language Result Execution time Memory
392985 2021-04-22T13:25:26 Z REALITYNB Stations (IOI20_stations) C++14
10 / 100
 1109 ms 648 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%1024,x/1024) ; 
}
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 436 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 5 ms 288 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 1109 ms 472 KB Output is correct
2 Correct 949 ms 492 KB Output is correct
3 Correct 720 ms 488 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 4 ms 472 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 643 ms 400 KB Output is correct
8 Correct 1093 ms 492 KB Output is correct
9 Correct 754 ms 492 KB Output is correct
10 Correct 689 ms 648 KB Output is correct
11 Correct 6 ms 472 KB Output is correct
12 Correct 7 ms 472 KB Output is correct
13 Correct 7 ms 484 KB Output is correct
14 Correct 3 ms 472 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 673 ms 488 KB Output is correct
17 Correct 599 ms 400 KB Output is correct
18 Correct 583 ms 400 KB Output is correct
19 Correct 635 ms 476 KB Output is correct
20 Correct 601 ms 488 KB Output is correct

Subtask #5
0 / 61.0

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