oj.uz

Submission #432007

# Submission time Handle Problem Language Result Execution time Memory
432007 2021-06-17T19:00:49 Z gonengazit Stations (IOI20_stations) C++14
100 / 100
 905 ms 956 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define x first
#define y second
vector<int> labels;
vector<vector<int>> g;
int tme;
void dfs1(int i,int f=0,int t=0){
	if(t==0){
		labels[i]=++tme;
	}
	for(auto u:g[i]){
		if(u!=f){
			dfs1(u,i,(t+1)%2);
		}
	}
	if(t==1){
		labels[i]=++tme;
	}
}

// void dfs1(int i, int f=0){
// 	int tin=++tme;
// 	for(auto u:g[i]){
// 		if(u!=f){
// 			dfs1(u,i);
// 		}
// 	}
// 	int tout=tme;
// 	labels[i]=tin*1000+tout;
// }
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	tme=-1;
	labels.assign(n,-1);
	g.assign(n,vector<int>());
	for(int i=0; i<n-1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}

	dfs1(0);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	
	int r=0;
	for(auto i:c){
		if(i<s){
			r=1;
		}
	}
	vector<pair<ii,int>> cld;
	int f=-1;
	if(r==0){
		int prev=s;
		for(auto i:c){
			int k=i;
			cld.emplace_back(ii(prev+1,k),i);
			prev=k;
		}
		if(s!=0){
			f=cld.back().y;
			cld.pop_back();
		}
	}
	else{
		f=c[0];
		for(int j=1; j<c.size(); j++){
			int i=c[j];
			int k=i;
			if(!cld.empty())
				cld.back().x.y=k-1;
			cld.emplace_back(ii(k,-1),i);
		}
		if(!cld.empty()){
			cld.back().x.y=s;
		}
	}

	for(auto i:cld){
		if(i.x.x<=t&&i.x.y>=t){
			return i.y;
		}
	}
	return f;
}
/*
1
5 100
0 1
1 2
1 3
2 4
3
0 1 2
1 2 2
1 4 2*/

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int j=1; j<c.size(); j++){
      |                ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 604 KB Output is correct
2 Correct 408 ms 648 KB Output is correct
3 Correct 845 ms 400 KB Output is correct
4 Correct 678 ms 400 KB Output is correct
5 Correct 567 ms 484 KB Output is correct
6 Correct 446 ms 684 KB Output is correct
7 Correct 461 ms 532 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 528 KB Output is correct
2 Correct 547 ms 548 KB Output is correct
3 Correct 831 ms 528 KB Output is correct
4 Correct 683 ms 492 KB Output is correct
5 Correct 569 ms 400 KB Output is correct
6 Correct 455 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 608 KB Output is correct
2 Correct 467 ms 608 KB Output is correct
3 Correct 845 ms 520 KB Output is correct
4 Correct 646 ms 412 KB Output is correct
5 Correct 586 ms 400 KB Output is correct
6 Correct 454 ms 520 KB Output is correct
7 Correct 472 ms 484 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 476 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 544 ms 400 KB Output is correct
12 Correct 451 ms 600 KB Output is correct
13 Correct 460 ms 684 KB Output is correct
14 Correct 410 ms 520 KB Output is correct
15 Correct 60 ms 416 KB Output is correct
16 Correct 66 ms 528 KB Output is correct
17 Correct 100 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 488 KB Output is correct
2 Correct 626 ms 400 KB Output is correct
3 Correct 569 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 464 KB Output is correct
6 Correct 2 ms 476 KB Output is correct
7 Correct 589 ms 488 KB Output is correct
8 Correct 905 ms 400 KB Output is correct
9 Correct 654 ms 400 KB Output is correct
10 Correct 596 ms 484 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 5 ms 448 KB Output is correct
13 Correct 4 ms 464 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 476 KB Output is correct
16 Correct 483 ms 488 KB Output is correct
17 Correct 477 ms 488 KB Output is correct
18 Correct 456 ms 488 KB Output is correct
19 Correct 488 ms 484 KB Output is correct
20 Correct 501 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 656 KB Output is correct
2 Correct 430 ms 616 KB Output is correct
3 Correct 849 ms 400 KB Output is correct
4 Correct 685 ms 600 KB Output is correct
5 Correct 544 ms 400 KB Output is correct
6 Correct 453 ms 604 KB Output is correct
7 Correct 466 ms 528 KB Output is correct
8 Correct 3 ms 464 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 439 ms 484 KB Output is correct
12 Correct 528 ms 488 KB Output is correct
13 Correct 876 ms 400 KB Output is correct
14 Correct 585 ms 400 KB Output is correct
15 Correct 572 ms 400 KB Output is correct
16 Correct 446 ms 480 KB Output is correct
17 Correct 575 ms 484 KB Output is correct
18 Correct 447 ms 528 KB Output is correct
19 Correct 484 ms 692 KB Output is correct
20 Correct 481 ms 528 KB Output is correct
21 Correct 51 ms 400 KB Output is correct
22 Correct 69 ms 528 KB Output is correct
23 Correct 114 ms 580 KB Output is correct
24 Correct 5 ms 468 KB Output is correct
25 Correct 5 ms 468 KB Output is correct
26 Correct 4 ms 468 KB Output is correct
27 Correct 4 ms 472 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 478 ms 472 KB Output is correct
30 Correct 510 ms 400 KB Output is correct
31 Correct 533 ms 400 KB Output is correct
32 Correct 518 ms 528 KB Output is correct
33 Correct 523 ms 528 KB Output is correct
34 Correct 331 ms 616 KB Output is correct
35 Correct 421 ms 724 KB Output is correct
36 Correct 468 ms 788 KB Output is correct
37 Correct 508 ms 696 KB Output is correct
38 Correct 454 ms 696 KB Output is correct
39 Correct 456 ms 916 KB Output is correct
40 Correct 422 ms 956 KB Output is correct
41 Correct 459 ms 676 KB Output is correct
42 Correct 70 ms 532 KB Output is correct
43 Correct 99 ms 656 KB Output is correct
44 Correct 121 ms 488 KB Output is correct
45 Correct 154 ms 484 KB Output is correct
46 Correct 304 ms 528 KB Output is correct
47 Correct 298 ms 488 KB Output is correct
48 Correct 67 ms 672 KB Output is correct
49 Correct 61 ms 676 KB Output is correct