oj.uz

Submission #1060571

# Submission time Handle Problem Language Result Execution time Memory
1060571 2024-08-15T17:20:30 Z Mihailo Stations (IOI20_stations) C++17
100 / 100
 636 ms 1196 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
#define pll pair<long long, long long>
#define MOD 1000000007
typedef long long ll;
using namespace std;
mt19937 mt(time(nullptr));
/*
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;
*/
vector<int> adj[2000];
bool d[2000];
ll mm, m[2000];

void mark(ll node) {
	m[node]=mm;
	mm++;
}

void dfsd(ll node, ll prev) {
	d[node]=!d[prev];
	for(int i=0; i<adj[node].size(); i++) {
		if(adj[node][i]!=prev) dfsd(adj[node][i], node);
	}
}

void euler(ll node, ll prev) {
	if(d[node]) mark(node);
	for(int i=0; i<adj[node].size(); i++) {
		if(adj[node][i]!=prev) euler(adj[node][i], node);
	}
	if(!d[node]) mark(node);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	for(int i=0; i<n; i++) adj[i].clear();
	for(int i=0; i<n; i++) d[i]=0;
	for(int i=0; i<n; i++) m[i]=0;
	mm=0;
	for(int i=0; i<n-1; i++) {
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	dfsd(0, 0);
	euler(0, 0);
	vector<int> rez;
	for(int i=0; i<n; i++) rez.pb(m[i]);
	return rez;
}

int find_next_station(int s, int t, vector<int> c) {
	if(c[0]>s) {
		if(t<s||t>=c[c.size()-1]) {
			return c[c.size()-1];
		}
		for(int i=0; i<c.size(); i++) {
			if(t<=c[i]) return c[i];
		}
	}
	else {
		if(t>s||t<=c[0]) {
			return c[0];
		}
		for(int i=c.size()-1; i>=0; i--) {
			if(t>=c[i]) return c[i];
		}
	}
}

Compilation message

stations.cpp: In function 'void dfsd(ll, ll)':
stations.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0; i<adj[node].size(); i++) {
      |               ~^~~~~~~~~~~~~~~~~
stations.cpp: In function 'void euler(ll, ll)':
stations.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0; i<adj[node].size(); i++) {
      |               ~^~~~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0; i<c.size(); i++) {
      |                ~^~~~~~~~~
stations.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 940 KB Output is correct
2 Correct 305 ms 940 KB Output is correct
3 Correct 585 ms 684 KB Output is correct
4 Correct 486 ms 684 KB Output is correct
5 Correct 372 ms 684 KB Output is correct
6 Correct 306 ms 940 KB Output is correct
7 Correct 324 ms 684 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 1 ms 776 KB Output is correct
10 Correct 0 ms 776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 688 KB Output is correct
2 Correct 337 ms 684 KB Output is correct
3 Correct 587 ms 684 KB Output is correct
4 Correct 460 ms 684 KB Output is correct
5 Correct 403 ms 684 KB Output is correct
6 Correct 290 ms 936 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 940 KB Output is correct
2 Correct 305 ms 940 KB Output is correct
3 Correct 636 ms 684 KB Output is correct
4 Correct 410 ms 684 KB Output is correct
5 Correct 394 ms 684 KB Output is correct
6 Correct 333 ms 940 KB Output is correct
7 Correct 309 ms 940 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 426 ms 684 KB Output is correct
12 Correct 325 ms 1080 KB Output is correct
13 Correct 302 ms 940 KB Output is correct
14 Correct 277 ms 684 KB Output is correct
15 Correct 31 ms 768 KB Output is correct
16 Correct 39 ms 768 KB Output is correct
17 Correct 62 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 684 KB Output is correct
2 Correct 439 ms 684 KB Output is correct
3 Correct 398 ms 684 KB Output is correct
4 Correct 1 ms 764 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 392 ms 684 KB Output is correct
8 Correct 613 ms 684 KB Output is correct
9 Correct 441 ms 688 KB Output is correct
10 Correct 424 ms 684 KB Output is correct
11 Correct 3 ms 776 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 2 ms 776 KB Output is correct
14 Correct 2 ms 836 KB Output is correct
15 Correct 1 ms 932 KB Output is correct
16 Correct 339 ms 684 KB Output is correct
17 Correct 335 ms 684 KB Output is correct
18 Correct 335 ms 684 KB Output is correct
19 Correct 362 ms 684 KB Output is correct
20 Correct 354 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 940 KB Output is correct
2 Correct 306 ms 940 KB Output is correct
3 Correct 578 ms 684 KB Output is correct
4 Correct 478 ms 684 KB Output is correct
5 Correct 401 ms 936 KB Output is correct
6 Correct 326 ms 940 KB Output is correct
7 Correct 313 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 0 ms 764 KB Output is correct
11 Correct 327 ms 908 KB Output is correct
12 Correct 361 ms 684 KB Output is correct
13 Correct 592 ms 688 KB Output is correct
14 Correct 447 ms 684 KB Output is correct
15 Correct 398 ms 684 KB Output is correct
16 Correct 316 ms 684 KB Output is correct
17 Correct 420 ms 684 KB Output is correct
18 Correct 297 ms 1080 KB Output is correct
19 Correct 313 ms 1072 KB Output is correct
20 Correct 271 ms 684 KB Output is correct
21 Correct 35 ms 764 KB Output is correct
22 Correct 40 ms 768 KB Output is correct
23 Correct 84 ms 716 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 2 ms 768 KB Output is correct
26 Correct 2 ms 764 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 1 ms 776 KB Output is correct
29 Correct 360 ms 684 KB Output is correct
30 Correct 353 ms 684 KB Output is correct
31 Correct 329 ms 684 KB Output is correct
32 Correct 333 ms 688 KB Output is correct
33 Correct 362 ms 684 KB Output is correct
34 Correct 221 ms 944 KB Output is correct
35 Correct 277 ms 940 KB Output is correct
36 Correct 303 ms 1080 KB Output is correct
37 Correct 290 ms 1080 KB Output is correct
38 Correct 307 ms 1188 KB Output is correct
39 Correct 306 ms 1096 KB Output is correct
40 Correct 320 ms 1088 KB Output is correct
41 Correct 325 ms 1196 KB Output is correct
42 Correct 35 ms 716 KB Output is correct
43 Correct 58 ms 764 KB Output is correct
44 Correct 78 ms 684 KB Output is correct
45 Correct 103 ms 768 KB Output is correct
46 Correct 206 ms 684 KB Output is correct
47 Correct 214 ms 684 KB Output is correct
48 Correct 28 ms 1028 KB Output is correct
49 Correct 27 ms 1020 KB Output is correct