oj.uz

Submission #416831

# Submission time Handle Problem Language Result Execution time Memory
416831 2021-06-03T03:32:51 Z Dilshod_Imomov Stations (IOI20_stations) C++17
100 / 100
 1087 ms 55824 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e3 + 7;

vector < int > tin, tout, d;
 
void dfs( vector<vector<int>> adj, int v, int p, int h, int &cnt ) {
	tin[v] = cnt++;
	d[v] = h;
	for ( auto u: adj[v] ) {
		if ( u != p ) {
			dfs( adj, u, v, h + 1, cnt );
		}
	}
	tout[v] = cnt++;
}
 
 
vector<int> label(int n, int k, vector<int> U, vector<int> V) {
	vector < vector < int > > adj(n + 1);
	tin.resize( n + 1 );
	tout.resize( n + 1 );
	d.resize( n + 1 );
	for ( int i = 0; i < n - 1; i++ ) {
		int u = U[i], v = V[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector < int > lb(n);
	int cnt = 0;
	dfs( adj, 0, -1, 0, cnt );
	vector < int > vc;
	for ( int i = 0; i < n; i++ ) {
		if ( d[i] & 1 ) {
			vc.push_back( tout[i] );
		}
		else {
			vc.push_back( tin[i] );
		}
	}
	sort( vc.begin(), vc.end() );
	int x = 0;
	map < int, int > mp;
	for ( auto i: vc ) {
		mp[i] = x++;
	}
	for ( int i = 0; i < n; i++ ) {
		if ( d[i] & 1 ) {
			lb[i] = mp[ tout[i] ];
		}
		else {
			lb[i] = mp[ tin[i] ];
		}
	}
	return lb;
}
 
int find_next_station(int s, int t, vector<int> c) {
	int sz = c.size(), pr = -1;
	int tins = -1, touts = -1;
	vector < int > tin(sz), tout(sz);
	if ( c[0] > s ) { // s is in even layer, s in tin
		tins = s;
		if ( s == 0 ) {
			touts = c.back() + 1;
		}
		else {
			touts = c[sz - 2] + 1;
			pr = c.back();
			c.pop_back();
			sz--;
		}
		tin[0] = tins + 1;
		tout[0] = c[0];
		for ( int i = 1; i < sz; i++ ) {
			tin[i] = tout[i - 1] + 1;
			tout[i] = c[i];
		}
	}
	else { // s in odd layer
		touts = s;
		if ( sz == 1 ) {
			tins = s - 1;
			return c[0];
		}
		else {
			pr = c[0];
			c.erase(c.begin());
			sz--;
			tins = c[0] - 1;
		}
		tout[sz - 1] = s - 1;
		tin[sz - 1] = c[sz - 1];
		for ( int i = sz - 2; i >= 0; i-- ) {
			tout[i] = tin[i + 1] - 1;
			tin[i] = c[i];
		}
	}
	// cout << tins << ' ' << touts << ' ' << pr << endl;
	for ( int i = 0; i < sz; i++ ) {
		int u = c[i];
		// cout << tin[i] << " " << tout[i] << endl;
		if ( tin[i] <= t && tout[i] >= t ) {
			return u;
		}
	}
	return pr;
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:62:17: warning: variable 'touts' set but not used [-Wunused-but-set-variable]
   62 |  int tins = -1, touts = -1;
      |                 ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 55432 KB Output is correct
2 Correct 1058 ms 55072 KB Output is correct
3 Correct 881 ms 468 KB Output is correct
4 Correct 653 ms 484 KB Output is correct
5 Correct 545 ms 464 KB Output is correct
6 Correct 1035 ms 49252 KB Output is correct
7 Correct 500 ms 41704 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 4 ms 476 KB Output is correct
10 Correct 2 ms 480 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 1352 KB Output is correct
2 Correct 564 ms 1112 KB Output is correct
3 Correct 883 ms 528 KB Output is correct
4 Correct 639 ms 400 KB Output is correct
5 Correct 567 ms 400 KB Output is correct
6 Correct 521 ms 1040 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 55436 KB Output is correct
2 Correct 998 ms 53156 KB Output is correct
3 Correct 824 ms 604 KB Output is correct
4 Correct 627 ms 492 KB Output is correct
5 Correct 570 ms 400 KB Output is correct
6 Correct 1027 ms 53420 KB Output is correct
7 Correct 496 ms 42632 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 4 ms 400 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 531 ms 404 KB Output is correct
12 Correct 994 ms 54320 KB Output is correct
13 Correct 1051 ms 50164 KB Output is correct
14 Correct 469 ms 3080 KB Output is correct
15 Correct 60 ms 400 KB Output is correct
16 Correct 200 ms 640 KB Output is correct
17 Correct 588 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 456 KB Output is correct
2 Correct 677 ms 400 KB Output is correct
3 Correct 562 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 559 ms 400 KB Output is correct
8 Correct 870 ms 456 KB Output is correct
9 Correct 625 ms 400 KB Output is correct
10 Correct 575 ms 528 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 8 ms 420 KB Output is correct
13 Correct 8 ms 448 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 4 ms 448 KB Output is correct
16 Correct 503 ms 400 KB Output is correct
17 Correct 513 ms 488 KB Output is correct
18 Correct 463 ms 400 KB Output is correct
19 Correct 443 ms 416 KB Output is correct
20 Correct 513 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 55576 KB Output is correct
2 Correct 1031 ms 48912 KB Output is correct
3 Correct 891 ms 524 KB Output is correct
4 Correct 666 ms 496 KB Output is correct
5 Correct 576 ms 508 KB Output is correct
6 Correct 974 ms 55628 KB Output is correct
7 Correct 530 ms 31112 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 472 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 955 ms 1156 KB Output is correct
12 Correct 592 ms 1028 KB Output is correct
13 Correct 842 ms 616 KB Output is correct
14 Correct 641 ms 528 KB Output is correct
15 Correct 578 ms 492 KB Output is correct
16 Correct 490 ms 1040 KB Output is correct
17 Correct 589 ms 536 KB Output is correct
18 Correct 978 ms 37460 KB Output is correct
19 Correct 1057 ms 51780 KB Output is correct
20 Correct 465 ms 4064 KB Output is correct
21 Correct 66 ms 424 KB Output is correct
22 Correct 219 ms 616 KB Output is correct
23 Correct 574 ms 668 KB Output is correct
24 Correct 4 ms 468 KB Output is correct
25 Correct 7 ms 468 KB Output is correct
26 Correct 4 ms 448 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 486 ms 492 KB Output is correct
30 Correct 496 ms 400 KB Output is correct
31 Correct 485 ms 528 KB Output is correct
32 Correct 505 ms 400 KB Output is correct
33 Correct 463 ms 488 KB Output is correct
34 Correct 855 ms 42044 KB Output is correct
35 Correct 1016 ms 55824 KB Output is correct
36 Correct 1052 ms 45868 KB Output is correct
37 Correct 1055 ms 13620 KB Output is correct
38 Correct 1087 ms 13384 KB Output is correct
39 Correct 1040 ms 17788 KB Output is correct
40 Correct 1026 ms 17784 KB Output is correct
41 Correct 1066 ms 14588 KB Output is correct
42 Correct 314 ms 688 KB Output is correct
43 Correct 584 ms 656 KB Output is correct
44 Correct 560 ms 1264 KB Output is correct
45 Correct 710 ms 1608 KB Output is correct
46 Correct 627 ms 13792 KB Output is correct
47 Correct 907 ms 26852 KB Output is correct
48 Correct 529 ms 1160 KB Output is correct
49 Correct 625 ms 1180 KB Output is correct