oj.uz

Submission #350219

# Submission time Handle Problem Language Result Execution time Memory
350219 2021-01-19T04:21:51 Z amunduzbaev Stations (IOI20_stations) C++14
100 / 100
 1140 ms 1504 KB 
#include "stations.h"
 
#ifndef EVAL
#include "stub.cpp"
#endif
 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
 
const int NN = 1e3+5;
 
vector<int> edges[NN];
int tim;
vector<int> val;
 
void dfs(int u, int t, int p){
	if(t) val[u] = ++tim;
	for(auto x:edges[u]){
		if(x == p) continue;
		dfs(x, (t ? 0 : 1), u);
	}
	if(!t) val[u] = ++tim;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i=0;i<n;i++) edges[i].clear();
	val.clear();
	for(int i=0;i<n-1;i++){
		edges[u[i]].pb(v[i]);
		edges[v[i]].pb(u[i]);
	}
	val.resize(n);
	tim = -1;
	dfs(0, 1, -1);
	//cout<<"passed\n";
	return val;
}
 
int find_next_station(int s, int t, vector<int> c){
	//sort(all(c));
	//cout<<s<<" "<<t<<"\n";
	//for(auto x:c) cout<<x<<" ";
	//cout<<"\n\n";
	
	if(s < c[0]){
		int p = c[sz(c)-1];
		if(t >= p || t < s) return p;
      	int i = 0;
      	while(c[i] < t && i < sz(c)-1) i++;
		return c[i];
	}
	else{
		int p = c[0];
		if(t > s || t < c[1]) return p; 
		int i = sz(c)-1;
		while(c[i] > t && i > 0) i--;
		return c[i];
	}
}
/*

1
5 10
0 1
1 2
2 3
3 4
3
1 3 
1 4 
0 1

1
5 10
0 1
1 2
1 3
2 4
2
0 2
1 3
 
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 992 KB Output is correct
2 Correct 468 ms 992 KB Output is correct
3 Correct 1140 ms 896 KB Output is correct
4 Correct 799 ms 864 KB Output is correct
5 Correct 530 ms 864 KB Output is correct
6 Correct 516 ms 992 KB Output is correct
7 Correct 537 ms 896 KB Output is correct
8 Correct 3 ms 960 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 864 KB Output is correct
2 Correct 543 ms 1056 KB Output is correct
3 Correct 1134 ms 864 KB Output is correct
4 Correct 726 ms 952 KB Output is correct
5 Correct 663 ms 748 KB Output is correct
6 Correct 467 ms 1028 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 992 KB Output is correct
2 Correct 459 ms 1012 KB Output is correct
3 Correct 939 ms 864 KB Output is correct
4 Correct 706 ms 952 KB Output is correct
5 Correct 702 ms 1108 KB Output is correct
6 Correct 433 ms 1292 KB Output is correct
7 Correct 453 ms 1240 KB Output is correct
8 Correct 3 ms 864 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 2 ms 1120 KB Output is correct
11 Correct 772 ms 736 KB Output is correct
12 Correct 500 ms 864 KB Output is correct
13 Correct 465 ms 1220 KB Output is correct
14 Correct 565 ms 864 KB Output is correct
15 Correct 70 ms 912 KB Output is correct
16 Correct 58 ms 864 KB Output is correct
17 Correct 112 ms 884 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 952 KB Output is correct
2 Correct 735 ms 736 KB Output is correct
3 Correct 586 ms 864 KB Output is correct
4 Correct 3 ms 992 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 2 ms 1248 KB Output is correct
7 Correct 718 ms 888 KB Output is correct
8 Correct 944 ms 736 KB Output is correct
9 Correct 807 ms 748 KB Output is correct
10 Correct 670 ms 864 KB Output is correct
11 Correct 6 ms 952 KB Output is correct
12 Correct 7 ms 952 KB Output is correct
13 Correct 6 ms 972 KB Output is correct
14 Correct 4 ms 960 KB Output is correct
15 Correct 2 ms 960 KB Output is correct
16 Correct 524 ms 952 KB Output is correct
17 Correct 509 ms 864 KB Output is correct
18 Correct 558 ms 736 KB Output is correct
19 Correct 597 ms 864 KB Output is correct
20 Correct 590 ms 864 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 864 KB Output is correct
2 Correct 487 ms 992 KB Output is correct
3 Correct 846 ms 1080 KB Output is correct
4 Correct 676 ms 1164 KB Output is correct
5 Correct 652 ms 960 KB Output is correct
6 Correct 525 ms 1100 KB Output is correct
7 Correct 520 ms 872 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 4 ms 864 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 462 ms 736 KB Output is correct
12 Correct 595 ms 1096 KB Output is correct
13 Correct 971 ms 1080 KB Output is correct
14 Correct 823 ms 824 KB Output is correct
15 Correct 670 ms 864 KB Output is correct
16 Correct 447 ms 900 KB Output is correct
17 Correct 761 ms 992 KB Output is correct
18 Correct 453 ms 1244 KB Output is correct
19 Correct 492 ms 1100 KB Output is correct
20 Correct 495 ms 900 KB Output is correct
21 Correct 72 ms 952 KB Output is correct
22 Correct 66 ms 864 KB Output is correct
23 Correct 142 ms 864 KB Output is correct
24 Correct 7 ms 952 KB Output is correct
25 Correct 6 ms 864 KB Output is correct
26 Correct 6 ms 864 KB Output is correct
27 Correct 4 ms 864 KB Output is correct
28 Correct 2 ms 952 KB Output is correct
29 Correct 581 ms 856 KB Output is correct
30 Correct 584 ms 952 KB Output is correct
31 Correct 541 ms 960 KB Output is correct
32 Correct 543 ms 952 KB Output is correct
33 Correct 563 ms 736 KB Output is correct
34 Correct 417 ms 1100 KB Output is correct
35 Correct 482 ms 1504 KB Output is correct
36 Correct 473 ms 1000 KB Output is correct
37 Correct 490 ms 1248 KB Output is correct
38 Correct 494 ms 1240 KB Output is correct
39 Correct 441 ms 992 KB Output is correct
40 Correct 494 ms 1004 KB Output is correct
41 Correct 535 ms 1140 KB Output is correct
42 Correct 63 ms 736 KB Output is correct
43 Correct 116 ms 736 KB Output is correct
44 Correct 120 ms 868 KB Output is correct
45 Correct 163 ms 864 KB Output is correct
46 Correct 329 ms 864 KB Output is correct
47 Correct 291 ms 868 KB Output is correct
48 Correct 80 ms 1084 KB Output is correct
49 Correct 70 ms 864 KB Output is correct