oj.uz

Submission #393002

# Submission time Handle Problem Language Result Execution time Memory
393002 2021-04-22T13:59:36 Z REALITYNB Stations (IOI20_stations) C++14
76 / 100
 1140 ms 812 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),  lvl(n) ; 
	function<void(int,int,int)> dfs = [&](int a, int p, int l){
		inn[a]=tim++ ; 
		lvl[a]=l ; 
		for(int x :adj[a]){
			if(x!=p){
				dfs(x,a,l^1) ; 
			}
		}
		outt[a]=tim++ ; 
	}; 
	dfs(0,0,0) ; 
	for(int i=0;i<n;i++)
		ans[i]=(lvl[i]?outt[i]:inn[i]) ; 
	return ans ; 
}
pii get(int x){
	return mp(x%(1<<11),(x>>11)) ; 
}
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){
	int isin = (ne[0]>s) ;
	if(s==0){
		for(int i=1;i<ne.size();i++) if(ne[i-1]<t&&t<=ne[i]) return ne[i] ; 
		return ne[0] ; 
	} 
	if(isin^1){

		for(int i=1;i+1<ne.size();i++){
			if(ne[i]<=t&&t<ne[i+1]){
				return ne[i] ; 
			}
		}
		if(ne.back()<=t&&t<s) return ne.back() ; 
		return ne[0] ; 
	}
	for(int i=1;i+1<ne.size();i++){
		if(ne[i-1]<t&&t<=ne[i]) return ne[i] ; 
	}	
	if(s<=t&&t<=ne[0]) return ne[0] ; 
	return ne.back() ; 

}
/*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 << res[i]<< " "<< res[j] << ": " << find_next_station(res[i],res[j],adj[i]) << endl ; 
			}
		}
	}
	return 0 ; 
}*/

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=1;i<ne.size();i++) if(ne[i-1]<t&&t<=ne[i]) return ne[i] ;
      |               ~^~~~~~~~~~
stations.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=1;i+1<ne.size();i++){
      |               ~~~^~~~~~~~~~
stations.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=1;i+1<ne.size();i++){
      |              ~~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 604 KB Output is correct
2 Correct 492 ms 612 KB Output is correct
3 Correct 1115 ms 480 KB Output is correct
4 Correct 865 ms 400 KB Output is correct
5 Correct 716 ms 400 KB Output is correct
6 Correct 562 ms 596 KB Output is correct
7 Correct 522 ms 656 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 5 ms 480 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 731 ms 400 KB Output is correct
12 Correct 574 ms 736 KB Output is correct
13 Correct 623 ms 728 KB Output is correct
14 Correct 441 ms 488 KB Output is correct
15 Correct 73 ms 452 KB Output is correct
16 Correct 89 ms 548 KB Output is correct
17 Correct 111 ms 548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1124 ms 400 KB Output is correct
2 Correct 943 ms 420 KB Output is correct
3 Correct 616 ms 492 KB Output is correct
4 Correct 4 ms 476 KB Output is correct
5 Correct 6 ms 480 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 694 ms 400 KB Output is correct
8 Correct 1016 ms 400 KB Output is correct
9 Correct 912 ms 492 KB Output is correct
10 Correct 715 ms 404 KB Output is correct
11 Correct 5 ms 472 KB Output is correct
12 Correct 7 ms 472 KB Output is correct
13 Correct 6 ms 484 KB Output is correct
14 Correct 5 ms 480 KB Output is correct
15 Correct 3 ms 480 KB Output is correct
16 Correct 548 ms 404 KB Output is correct
17 Correct 652 ms 400 KB Output is correct
18 Correct 648 ms 492 KB Output is correct
19 Correct 640 ms 488 KB Output is correct
20 Correct 685 ms 488 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 639 ms 648 KB Partially correct
2 Partially correct 528 ms 656 KB Partially correct
3 Correct 1140 ms 472 KB Output is correct
4 Correct 691 ms 476 KB Output is correct
5 Correct 801 ms 400 KB Output is correct
6 Partially correct 542 ms 724 KB Partially correct
7 Partially correct 445 ms 624 KB Partially correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 4 ms 480 KB Output is correct
10 Correct 2 ms 480 KB Output is correct
11 Partially correct 503 ms 528 KB Partially correct
12 Partially correct 551 ms 528 KB Partially correct
13 Correct 922 ms 500 KB Output is correct
14 Correct 675 ms 400 KB Output is correct
15 Correct 693 ms 492 KB Output is correct
16 Partially correct 497 ms 492 KB Partially correct
17 Correct 633 ms 464 KB Output is correct
18 Partially correct 565 ms 620 KB Partially correct
19 Partially correct 506 ms 692 KB Partially correct
20 Partially correct 555 ms 528 KB Partially correct
21 Correct 76 ms 400 KB Output is correct
22 Partially correct 89 ms 532 KB Partially correct
23 Partially correct 150 ms 660 KB Partially correct
24 Correct 6 ms 480 KB Output is correct
25 Correct 7 ms 472 KB Output is correct
26 Correct 8 ms 472 KB Output is correct
27 Correct 5 ms 480 KB Output is correct
28 Correct 2 ms 472 KB Output is correct
29 Correct 593 ms 400 KB Output is correct
30 Correct 651 ms 472 KB Output is correct
31 Correct 578 ms 400 KB Output is correct
32 Correct 679 ms 492 KB Output is correct
33 Correct 608 ms 528 KB Output is correct
34 Partially correct 407 ms 688 KB Partially correct
35 Partially correct 562 ms 608 KB Partially correct
36 Partially correct 607 ms 624 KB Partially correct
37 Partially correct 466 ms 612 KB Partially correct
38 Partially correct 508 ms 660 KB Partially correct
39 Partially correct 547 ms 712 KB Partially correct
40 Partially correct 517 ms 812 KB Partially correct
41 Partially correct 554 ms 648 KB Partially correct
42 Partially correct 62 ms 528 KB Partially correct
43 Partially correct 112 ms 500 KB Partially correct
44 Partially correct 165 ms 528 KB Partially correct
45 Partially correct 198 ms 588 KB Partially correct
46 Partially correct 392 ms 528 KB Partially correct
47 Partially correct 444 ms 640 KB Partially correct
48 Partially correct 66 ms 552 KB Partially correct
49 Partially correct 90 ms 644 KB Partially correct