oj.uz

답안 #392978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392978 2021-04-22T13:21:16 Z REALITYNB 기지국 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 664 ms 620 KB Wrong query response.
2 Halted 0 ms 0 KB -