oj.uz

Submission #680851

# Submission time Handle Problem Language Result Execution time Memory
680851 2023-01-11T21:47:14 Z aryan12 Stations (IOI20_stations) C++17
100 / 100
 871 ms 856 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

const int N = 1001;
int tin[N], tout[N], depth[N];
int tim = -1;
vector<int> g[N];

void dfs(int node, int par)
{
	tin[node] = (depth[node] % 2 == 1) ? ++tim : tim;
	for(int to: g[node])
	{
		if(to == par) continue;
		depth[to] = depth[node] + 1;
		dfs(to, node);
	}
	tout[node] = (depth[node] % 2 == 0) ? ++tim : tim;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	tim = -1;
	for(int i = 0; i < N; i++)
	{
		g[i].clear();
	}
	for(int i = 0; i < u.size(); i++)
	{
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	depth[0] = 1;
	dfs(0, -1);
	vector<int> labels;
	for(int i = 0; i < n; i++)
	{
		if(depth[i] % 2 == 1)
		{
			labels.push_back(tin[i]);
		}
		else
		{
			labels.push_back(tout[i]);
		}
	}
	return labels;
}

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

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < u.size(); i++)
      |                 ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i = 0; i < c.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 532 KB Output is correct
2 Correct 467 ms 532 KB Output is correct
3 Correct 821 ms 524 KB Output is correct
4 Correct 668 ms 544 KB Output is correct
5 Correct 573 ms 532 KB Output is correct
6 Correct 443 ms 560 KB Output is correct
7 Correct 429 ms 536 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 544 KB Output is correct
2 Correct 534 ms 548 KB Output is correct
3 Correct 813 ms 520 KB Output is correct
4 Correct 623 ms 544 KB Output is correct
5 Correct 593 ms 524 KB Output is correct
6 Correct 396 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 544 KB Output is correct
2 Correct 450 ms 548 KB Output is correct
3 Correct 758 ms 524 KB Output is correct
4 Correct 648 ms 512 KB Output is correct
5 Correct 495 ms 528 KB Output is correct
6 Correct 452 ms 660 KB Output is correct
7 Correct 372 ms 536 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 571 ms 416 KB Output is correct
12 Correct 492 ms 856 KB Output is correct
13 Correct 498 ms 764 KB Output is correct
14 Correct 429 ms 548 KB Output is correct
15 Correct 47 ms 620 KB Output is correct
16 Correct 50 ms 672 KB Output is correct
17 Correct 113 ms 676 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 420 KB Output is correct
2 Correct 668 ms 520 KB Output is correct
3 Correct 524 ms 544 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 5 ms 628 KB Output is correct
6 Correct 0 ms 624 KB Output is correct
7 Correct 579 ms 420 KB Output is correct
8 Correct 842 ms 520 KB Output is correct
9 Correct 736 ms 544 KB Output is correct
10 Correct 578 ms 544 KB Output is correct
11 Correct 4 ms 628 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 4 ms 620 KB Output is correct
15 Correct 1 ms 620 KB Output is correct
16 Correct 530 ms 660 KB Output is correct
17 Correct 565 ms 544 KB Output is correct
18 Correct 549 ms 544 KB Output is correct
19 Correct 506 ms 416 KB Output is correct
20 Correct 444 ms 524 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 664 KB Output is correct
2 Correct 426 ms 524 KB Output is correct
3 Correct 827 ms 536 KB Output is correct
4 Correct 671 ms 532 KB Output is correct
5 Correct 553 ms 416 KB Output is correct
6 Correct 410 ms 548 KB Output is correct
7 Correct 398 ms 544 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 0 ms 632 KB Output is correct
11 Correct 462 ms 572 KB Output is correct
12 Correct 485 ms 624 KB Output is correct
13 Correct 733 ms 528 KB Output is correct
14 Correct 667 ms 524 KB Output is correct
15 Correct 582 ms 544 KB Output is correct
16 Correct 405 ms 544 KB Output is correct
17 Correct 585 ms 548 KB Output is correct
18 Correct 411 ms 748 KB Output is correct
19 Correct 414 ms 776 KB Output is correct
20 Correct 380 ms 524 KB Output is correct
21 Correct 46 ms 620 KB Output is correct
22 Correct 55 ms 544 KB Output is correct
23 Correct 98 ms 548 KB Output is correct
24 Correct 4 ms 628 KB Output is correct
25 Correct 4 ms 620 KB Output is correct
26 Correct 3 ms 620 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 1 ms 620 KB Output is correct
29 Correct 491 ms 548 KB Output is correct
30 Correct 484 ms 416 KB Output is correct
31 Correct 433 ms 524 KB Output is correct
32 Correct 514 ms 532 KB Output is correct
33 Correct 506 ms 528 KB Output is correct
34 Correct 331 ms 544 KB Output is correct
35 Correct 399 ms 644 KB Output is correct
36 Correct 434 ms 628 KB Output is correct
37 Correct 345 ms 640 KB Output is correct
38 Correct 468 ms 636 KB Output is correct
39 Correct 427 ms 740 KB Output is correct
40 Correct 379 ms 668 KB Output is correct
41 Correct 438 ms 644 KB Output is correct
42 Correct 62 ms 620 KB Output is correct
43 Correct 95 ms 528 KB Output is correct
44 Correct 125 ms 572 KB Output is correct
45 Correct 150 ms 636 KB Output is correct
46 Correct 301 ms 548 KB Output is correct
47 Correct 310 ms 532 KB Output is correct
48 Correct 60 ms 676 KB Output is correct
49 Correct 64 ms 672 KB Output is correct