oj.uz

Submission #923662

# Submission time Handle Problem Language Result Execution time Memory
923662 2024-02-07T14:35:01 Z oblantis Stations (IOI20_stations) C++17
100 / 100
 675 ms 1884 KB 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e4 + 1;
//#include "stations.h"
bool wt[maxn];
vt<int> g[maxn];
vt<pii> asgn;
int in[maxn], out[maxn], cnt;
void dfs(int i, int p){
	in[i] = cnt++;
	for(auto j : g[i]){
		if(j == p)continue;
		wt[j] = wt[i] ^ 1;
		dfs(j, i);
	}
	out[i] = cnt++;
	if(wt[i])asgn.pb({out[i], i});
	else asgn.pb({in[i], i});
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	cnt = 0;
	asgn.clear();
	for(int i = 0; i <= n; i++)g[i].clear();
	for(int i = 0; i < n - 1; i++){
		g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
	}
	wt[0] = 0;
	dfs(0, -1);
	cnt = 0;
	sort(all(asgn));
	for(auto i : asgn){
		labels[i.ss] = cnt++;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(all(c));
	if(s < c[0]){
		for(auto i : c){
			if(s <= t && t <= i)return i;
		}
		return c.back();
	}
	else {
		reverse(all(c));
		for(auto i : c){
			if(s >= t && t >= i)return i;
		}
		return c.back();
	}
}

//void solve() {
	
//}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int times = 1;
	////cin >> times;
	//for(int i = 1; i <= times; i++) {
		//solve();
	//}
	//return 0;
//}
//#include "stations.h"
//#include <cstdio>
//#include <cassert>
//#include <map>
//#include <vector>
//#include <algorithm>

//static int max_label = 0;
//static int r, n, k, q;
//static std::vector<int> u, v, labels, answers;
//static std::map<int, int> reverse_labels;
//static std::vector<std::vector<int>> adjlist;
//static int s, t, w;
//static std::vector<int> c;

//int main() {
	//assert(scanf("%d", &r) == 1);
	//for (int tc = 0; tc < r; tc++) {
		//assert(scanf("%d%d", &n, &k) == 2);
		//u.resize(n - 1);
		//v.resize(n - 1);
		//adjlist.clear();
		//adjlist.resize(n);
		//for (int i = 0; i < n - 1; i++) {
			//assert(scanf("%d%d", &u[i], &v[i]) == 2);
			//adjlist[u[i]].push_back(v[i]);
			//adjlist[v[i]].push_back(u[i]);
		//}
		//labels = label(n, k, u, v);
		//if ((int)labels.size() != n) {
			//printf("Number of labels not equal to %d\n", n);
			//exit(0);
		//}
		//reverse_labels.clear();
		//for (int i = 0; i < n; i++) {
			//if (labels[i] < 0 || labels[i] > k) {
				//printf("Label not in range 0 to %d\n", k);
				//exit(0);
			//}
			//if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				//printf("Labels not unique\n");
				//exit(0);
			//}
			//reverse_labels[labels[i]] = i;
			//if (labels[i] > max_label) {
				//max_label = labels[i];
			//}
		//}
		//assert(scanf("%d", &q) == 1);
		//for (int i = 0; i < q; i++) {
			//assert(scanf("%d%d%d", &s, &t, &w) == 3);
			//c.clear();
			//for (int v : adjlist[s]) {
				//c.push_back(labels[v]);
			//}
			//std::sort(c.begin(), c.end());
			//int answer = find_next_station(labels[s], labels[t], c);
			//if (!std::binary_search(c.begin(), c.end(), answer)) {
				//printf("Label %d returned by find_next_station not found in c\n", answer);
				//exit(0);
			//}
			//answers.push_back(reverse_labels[answer]);
		//}
	//}
	//printf("%d\n", max_label);
	//for (int index : answers) {
		//printf("%d\n", index);
	//}
	//exit(0);
//}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 1448 KB Output is correct
2 Correct 278 ms 1448 KB Output is correct
3 Correct 556 ms 1196 KB Output is correct
4 Correct 420 ms 1200 KB Output is correct
5 Correct 391 ms 1448 KB Output is correct
6 Correct 259 ms 1428 KB Output is correct
7 Correct 259 ms 1448 KB Output is correct
8 Correct 2 ms 1284 KB Output is correct
9 Correct 3 ms 1280 KB Output is correct
10 Correct 1 ms 1284 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1364 KB Output is correct
2 Correct 371 ms 1292 KB Output is correct
3 Correct 567 ms 1452 KB Output is correct
4 Correct 394 ms 1196 KB Output is correct
5 Correct 358 ms 1196 KB Output is correct
6 Correct 253 ms 1284 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 1640 KB Output is correct
2 Correct 278 ms 1628 KB Output is correct
3 Correct 675 ms 1452 KB Output is correct
4 Correct 390 ms 1196 KB Output is correct
5 Correct 373 ms 1196 KB Output is correct
6 Correct 257 ms 1624 KB Output is correct
7 Correct 297 ms 1196 KB Output is correct
8 Correct 2 ms 1284 KB Output is correct
9 Correct 3 ms 1284 KB Output is correct
10 Correct 1 ms 1280 KB Output is correct
11 Correct 348 ms 1196 KB Output is correct
12 Correct 263 ms 1620 KB Output is correct
13 Correct 281 ms 1768 KB Output is correct
14 Correct 299 ms 1376 KB Output is correct
15 Correct 33 ms 1276 KB Output is correct
16 Correct 36 ms 1536 KB Output is correct
17 Correct 56 ms 1412 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 1196 KB Output is correct
2 Correct 492 ms 1196 KB Output is correct
3 Correct 337 ms 1196 KB Output is correct
4 Correct 1 ms 1284 KB Output is correct
5 Correct 3 ms 1480 KB Output is correct
6 Correct 0 ms 1280 KB Output is correct
7 Correct 399 ms 1200 KB Output is correct
8 Correct 555 ms 1196 KB Output is correct
9 Correct 430 ms 1196 KB Output is correct
10 Correct 412 ms 1196 KB Output is correct
11 Correct 3 ms 1284 KB Output is correct
12 Correct 5 ms 1284 KB Output is correct
13 Correct 3 ms 1284 KB Output is correct
14 Correct 3 ms 1284 KB Output is correct
15 Correct 0 ms 1284 KB Output is correct
16 Correct 304 ms 1196 KB Output is correct
17 Correct 353 ms 1196 KB Output is correct
18 Correct 315 ms 1196 KB Output is correct
19 Correct 383 ms 1196 KB Output is correct
20 Correct 312 ms 1196 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 1448 KB Output is correct
2 Correct 281 ms 1440 KB Output is correct
3 Correct 516 ms 1196 KB Output is correct
4 Correct 420 ms 1196 KB Output is correct
5 Correct 401 ms 1196 KB Output is correct
6 Correct 330 ms 1448 KB Output is correct
7 Correct 320 ms 1196 KB Output is correct
8 Correct 1 ms 1276 KB Output is correct
9 Correct 3 ms 1292 KB Output is correct
10 Correct 0 ms 1284 KB Output is correct
11 Correct 326 ms 1364 KB Output is correct
12 Correct 397 ms 1332 KB Output is correct
13 Correct 524 ms 1196 KB Output is correct
14 Correct 403 ms 1196 KB Output is correct
15 Correct 431 ms 1196 KB Output is correct
16 Correct 277 ms 1196 KB Output is correct
17 Correct 401 ms 1196 KB Output is correct
18 Correct 282 ms 1444 KB Output is correct
19 Correct 273 ms 1516 KB Output is correct
20 Correct 255 ms 1196 KB Output is correct
21 Correct 37 ms 1536 KB Output is correct
22 Correct 40 ms 1416 KB Output is correct
23 Correct 63 ms 1820 KB Output is correct
24 Correct 4 ms 1284 KB Output is correct
25 Correct 3 ms 1532 KB Output is correct
26 Correct 3 ms 1280 KB Output is correct
27 Correct 3 ms 1284 KB Output is correct
28 Correct 1 ms 1284 KB Output is correct
29 Correct 348 ms 1196 KB Output is correct
30 Correct 316 ms 1196 KB Output is correct
31 Correct 369 ms 1196 KB Output is correct
32 Correct 316 ms 1196 KB Output is correct
33 Correct 337 ms 1196 KB Output is correct
34 Correct 206 ms 1428 KB Output is correct
35 Correct 263 ms 1884 KB Output is correct
36 Correct 272 ms 1504 KB Output is correct
37 Correct 309 ms 1468 KB Output is correct
38 Correct 339 ms 1732 KB Output is correct
39 Correct 276 ms 1660 KB Output is correct
40 Correct 303 ms 1660 KB Output is correct
41 Correct 310 ms 1728 KB Output is correct
42 Correct 33 ms 1440 KB Output is correct
43 Correct 65 ms 1364 KB Output is correct
44 Correct 103 ms 1396 KB Output is correct
45 Correct 85 ms 1424 KB Output is correct
46 Correct 207 ms 1196 KB Output is correct
47 Correct 210 ms 1408 KB Output is correct
48 Correct 47 ms 1500 KB Output is correct
49 Correct 45 ms 1812 KB Output is correct