oj.uz

Submission #1042590

# Submission time Handle Problem Language Result Execution time Memory
1042590 2024-08-03T08:09:16 Z AmirAli_H1 Stations (IOI20_stations) C++17
100 / 100
 554 ms 1332 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "stations.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2000 + 4;

int n, k;
vector<int> adj[maxn];
int h[maxn], timer;
vector<int> A;

void dfs(int v, int p = -1) {
	if (h[v] % 2 == 0) A[v] = timer++;
	for (int u : adj[v]) {
		if (u == p) continue;
		h[u] = h[v] + 1;
		dfs(u, v);
	}
	if (h[v] % 2 == 1) A[v] = timer++;
}

vector<int> label(int Nx, int Kx, vector<int> ux, vector<int> vx) {
	n = Nx; k = Kx;
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < n - 1; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
	}
	A.clear(); A.resize(n);
	timer = 0; dfs(0);
	return A;
}

int find_next_station(int s, int t, vector<int> ls) {
	if (len(ls) == 1) return ls[0];
	
	sort(all(ls));
	if (ls[0] > s) {
		int p = ls.back(); ls.pop_back();
		int l = s + 1;
		for (int r : ls) {
			if (t >= l && t <= r) return r;
			l = r + 1;
		}
		return p;
	}
	else {
		reverse(all(ls));
		int p = ls.back(); ls.pop_back();
		int r = s - 1;
		for (int l : ls) {
			if (t >= l && t <= r) return l;
			r = l - 1;
		}
		return p;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 1204 KB Output is correct
2 Correct 260 ms 940 KB Output is correct
3 Correct 513 ms 684 KB Output is correct
4 Correct 382 ms 688 KB Output is correct
5 Correct 371 ms 684 KB Output is correct
6 Correct 238 ms 940 KB Output is correct
7 Correct 245 ms 684 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 680 KB Output is correct
2 Correct 277 ms 684 KB Output is correct
3 Correct 508 ms 684 KB Output is correct
4 Correct 411 ms 688 KB Output is correct
5 Correct 342 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 302 ms 940 KB Output is correct
2 Correct 254 ms 940 KB Output is correct
3 Correct 530 ms 684 KB Output is correct
4 Correct 422 ms 684 KB Output is correct
5 Correct 353 ms 684 KB Output is correct
6 Correct 230 ms 940 KB Output is correct
7 Correct 255 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 1 ms 768 KB Output is correct
11 Correct 344 ms 684 KB Output is correct
12 Correct 283 ms 1076 KB Output is correct
13 Correct 251 ms 1192 KB Output is correct
14 Correct 265 ms 688 KB Output is correct
15 Correct 21 ms 764 KB Output is correct
16 Correct 29 ms 768 KB Output is correct
17 Correct 47 ms 684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 684 KB Output is correct
2 Correct 363 ms 936 KB Output is correct
3 Correct 361 ms 684 KB Output is correct
4 Correct 1 ms 1016 KB Output is correct
5 Correct 2 ms 776 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 358 ms 684 KB Output is correct
8 Correct 499 ms 684 KB Output is correct
9 Correct 367 ms 684 KB Output is correct
10 Correct 359 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 2 ms 776 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 319 ms 684 KB Output is correct
17 Correct 256 ms 684 KB Output is correct
18 Correct 213 ms 684 KB Output is correct
19 Correct 256 ms 684 KB Output is correct
20 Correct 292 ms 692 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 940 KB Output is correct
2 Correct 258 ms 940 KB Output is correct
3 Correct 519 ms 684 KB Output is correct
4 Correct 420 ms 684 KB Output is correct
5 Correct 322 ms 684 KB Output is correct
6 Correct 288 ms 940 KB Output is correct
7 Correct 247 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 776 KB Output is correct
11 Correct 252 ms 684 KB Output is correct
12 Correct 318 ms 684 KB Output is correct
13 Correct 507 ms 684 KB Output is correct
14 Correct 382 ms 684 KB Output is correct
15 Correct 377 ms 684 KB Output is correct
16 Correct 278 ms 684 KB Output is correct
17 Correct 307 ms 684 KB Output is correct
18 Correct 257 ms 820 KB Output is correct
19 Correct 246 ms 1076 KB Output is correct
20 Correct 261 ms 684 KB Output is correct
21 Correct 24 ms 768 KB Output is correct
22 Correct 42 ms 768 KB Output is correct
23 Correct 47 ms 768 KB Output is correct
24 Correct 3 ms 764 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 1 ms 764 KB Output is correct
27 Correct 2 ms 780 KB Output is correct
28 Correct 0 ms 768 KB Output is correct
29 Correct 304 ms 704 KB Output is correct
30 Correct 315 ms 684 KB Output is correct
31 Correct 287 ms 684 KB Output is correct
32 Correct 291 ms 684 KB Output is correct
33 Correct 321 ms 684 KB Output is correct
34 Correct 162 ms 940 KB Output is correct
35 Correct 264 ms 940 KB Output is correct
36 Correct 266 ms 1188 KB Output is correct
37 Correct 262 ms 940 KB Output is correct
38 Correct 255 ms 1192 KB Output is correct
39 Correct 256 ms 836 KB Output is correct
40 Correct 251 ms 1332 KB Output is correct
41 Correct 241 ms 1076 KB Output is correct
42 Correct 32 ms 768 KB Output is correct
43 Correct 41 ms 768 KB Output is correct
44 Correct 66 ms 740 KB Output is correct
45 Correct 102 ms 744 KB Output is correct
46 Correct 172 ms 688 KB Output is correct
47 Correct 169 ms 716 KB Output is correct
48 Correct 26 ms 1012 KB Output is correct
49 Correct 24 ms 1176 KB Output is correct