oj.uz

Submission #1001132

# Submission time Handle Problem Language Result Execution time Memory
1001132 2024-06-18T15:19:34 Z ZeroCool Stations (IOI20_stations) C++14
100 / 100
 657 ms 1124 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

vector<int> g[N];
vector<int> A;

int T = 0;
void dfs(int x,int p, bool b){
	if(b){
		for(auto u: g[x]){
			if(u == p)continue;
			dfs(u, x, !b);
		}
		A[x] = T++;
	}else{
		A[x] = T++;
		for(auto u: g[x]){
			if(u == p)continue;
			dfs(u, x, !b);
		}
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	T = 0;
	A.clear();
	A.resize(n);
	for(int i = 0;i < n;i++)g[i].clear();
	for(int i = 0;i < n- 1;i ++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(0, 0,0 );
	return A;
}

int find_next_station(int s, int t, std::vector<int> g) {
	if(g.size() == 1)return g.front();
	sort(g.begin(), g.end());
	if(s > g.front()){
		if(t > s || t <= g.front())return g.front();
		return *(upper_bound(g.begin(), g.end(), t) - 1);
	}else{
		if(t < s | t >= g.back())return g.back();
		return *lower_bound(g.begin(), g.end(), t);
	}
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:49:8: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   49 |   if(t < s | t >= g.back())return g.back();
      |      ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 684 KB Output is correct
2 Correct 266 ms 792 KB Output is correct
3 Correct 483 ms 684 KB Output is correct
4 Correct 350 ms 684 KB Output is correct
5 Correct 334 ms 684 KB Output is correct
6 Correct 270 ms 684 KB Output is correct
7 Correct 287 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 684 KB Output is correct
2 Correct 279 ms 684 KB Output is correct
3 Correct 529 ms 684 KB Output is correct
4 Correct 424 ms 800 KB Output is correct
5 Correct 389 ms 684 KB Output is correct
6 Correct 271 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 684 KB Output is correct
2 Correct 277 ms 684 KB Output is correct
3 Correct 607 ms 684 KB Output is correct
4 Correct 458 ms 696 KB Output is correct
5 Correct 375 ms 684 KB Output is correct
6 Correct 259 ms 684 KB Output is correct
7 Correct 272 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 367 ms 684 KB Output is correct
12 Correct 324 ms 796 KB Output is correct
13 Correct 334 ms 684 KB Output is correct
14 Correct 270 ms 684 KB Output is correct
15 Correct 26 ms 764 KB Output is correct
16 Correct 34 ms 772 KB Output is correct
17 Correct 56 ms 744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 684 KB Output is correct
2 Correct 379 ms 684 KB Output is correct
3 Correct 337 ms 940 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 342 ms 796 KB Output is correct
8 Correct 520 ms 684 KB Output is correct
9 Correct 390 ms 800 KB Output is correct
10 Correct 299 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 292 ms 684 KB Output is correct
17 Correct 294 ms 684 KB Output is correct
18 Correct 311 ms 684 KB Output is correct
19 Correct 311 ms 684 KB Output is correct
20 Correct 308 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 684 KB Output is correct
2 Correct 273 ms 684 KB Output is correct
3 Correct 504 ms 684 KB Output is correct
4 Correct 411 ms 684 KB Output is correct
5 Correct 320 ms 684 KB Output is correct
6 Correct 279 ms 684 KB Output is correct
7 Correct 249 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 1 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 287 ms 684 KB Output is correct
12 Correct 370 ms 684 KB Output is correct
13 Correct 593 ms 684 KB Output is correct
14 Correct 410 ms 684 KB Output is correct
15 Correct 345 ms 684 KB Output is correct
16 Correct 320 ms 688 KB Output is correct
17 Correct 365 ms 684 KB Output is correct
18 Correct 341 ms 788 KB Output is correct
19 Correct 337 ms 932 KB Output is correct
20 Correct 307 ms 684 KB Output is correct
21 Correct 32 ms 768 KB Output is correct
22 Correct 38 ms 744 KB Output is correct
23 Correct 56 ms 744 KB Output is correct
24 Correct 2 ms 764 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 2 ms 776 KB Output is correct
27 Correct 1 ms 764 KB Output is correct
28 Correct 1 ms 776 KB Output is correct
29 Correct 308 ms 796 KB Output is correct
30 Correct 337 ms 684 KB Output is correct
31 Correct 318 ms 684 KB Output is correct
32 Correct 331 ms 684 KB Output is correct
33 Correct 363 ms 684 KB Output is correct
34 Correct 227 ms 684 KB Output is correct
35 Correct 272 ms 684 KB Output is correct
36 Correct 290 ms 684 KB Output is correct
37 Correct 313 ms 1124 KB Output is correct
38 Correct 280 ms 932 KB Output is correct
39 Correct 307 ms 1048 KB Output is correct
40 Correct 274 ms 796 KB Output is correct
41 Correct 304 ms 932 KB Output is correct
42 Correct 48 ms 768 KB Output is correct
43 Correct 64 ms 768 KB Output is correct
44 Correct 80 ms 768 KB Output is correct
45 Correct 100 ms 716 KB Output is correct
46 Correct 207 ms 684 KB Output is correct
47 Correct 189 ms 684 KB Output is correct
48 Correct 33 ms 768 KB Output is correct
49 Correct 34 ms 836 KB Output is correct