oj.uz

Submission #306171

# Submission time Handle Problem Language Result Execution time Memory
306171 2020-09-24T18:59:17 Z aljasdlas Stations (IOI20_stations) C++14
100 / 100
 1081 ms 1280 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> AdjList;
vector<int> labels;
int curLabel;

void dfs(int u, int p, int d) {
	if(d%2==0)
		labels[u] = curLabel++;

    for(auto v: AdjList[u]) {
            if(v != p)
                dfs(v, u, d+1);
    }

	if(d%2)
		labels[u] = curLabel++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	// n = 10;
	// u.resize(n);
	// v.resize(n);

    AdjList.assign(n, vector<int>(0));
	labels.assign(n,-1);
    curLabel = 0;

    for(int i = 0; i < n-1; i++) {
        AdjList[u[i]].push_back(v[i]);
        AdjList[v[i]].push_back(u[i]);
    }
    
	dfs(0, -1, 0);

	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(c.begin(), c.end());

	for(auto x: c)
		if(x == t)
			return x;
	if(c.size() == 0)
		return c[0];
	
	if(s < c[0]) {
		if(t < s) return c.back();

		for(int i = 0; i < c.size()-1; i++)
			if(t < c[i])
				return c[i];

		return c.back();
	} else {
		if(t > s) return c[0];

		for(int i = c.size()-1; i > 0; i--)
			if(t > c[i])
				return c[i];

		return c[0];
	}
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 1024 KB Output is correct
2 Correct 467 ms 1008 KB Output is correct
3 Correct 1029 ms 648 KB Output is correct
4 Correct 839 ms 648 KB Output is correct
5 Correct 731 ms 652 KB Output is correct
6 Correct 487 ms 1024 KB Output is correct
7 Correct 572 ms 768 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 4 ms 656 KB Output is correct
10 Correct 1 ms 652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 768 KB Output is correct
2 Correct 627 ms 820 KB Output is correct
3 Correct 1027 ms 776 KB Output is correct
4 Correct 767 ms 772 KB Output is correct
5 Correct 688 ms 776 KB Output is correct
6 Correct 472 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 1024 KB Output is correct
2 Correct 587 ms 1024 KB Output is correct
3 Correct 938 ms 640 KB Output is correct
4 Correct 769 ms 640 KB Output is correct
5 Correct 746 ms 640 KB Output is correct
6 Correct 557 ms 1024 KB Output is correct
7 Correct 485 ms 780 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 4 ms 644 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 659 ms 640 KB Output is correct
12 Correct 538 ms 1124 KB Output is correct
13 Correct 547 ms 1024 KB Output is correct
14 Correct 514 ms 828 KB Output is correct
15 Correct 53 ms 768 KB Output is correct
16 Correct 76 ms 852 KB Output is correct
17 Correct 146 ms 808 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 776 KB Output is correct
2 Correct 866 ms 652 KB Output is correct
3 Correct 753 ms 640 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 2 ms 776 KB Output is correct
7 Correct 689 ms 640 KB Output is correct
8 Correct 947 ms 776 KB Output is correct
9 Correct 801 ms 644 KB Output is correct
10 Correct 645 ms 640 KB Output is correct
11 Correct 5 ms 900 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 5 ms 652 KB Output is correct
14 Correct 4 ms 652 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 546 ms 640 KB Output is correct
17 Correct 505 ms 776 KB Output is correct
18 Correct 540 ms 768 KB Output is correct
19 Correct 580 ms 792 KB Output is correct
20 Correct 559 ms 648 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 1024 KB Output is correct
2 Correct 515 ms 1024 KB Output is correct
3 Correct 945 ms 648 KB Output is correct
4 Correct 709 ms 644 KB Output is correct
5 Correct 659 ms 648 KB Output is correct
6 Correct 545 ms 1024 KB Output is correct
7 Correct 600 ms 784 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 772 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 481 ms 776 KB Output is correct
12 Correct 631 ms 828 KB Output is correct
13 Correct 1081 ms 648 KB Output is correct
14 Correct 674 ms 640 KB Output is correct
15 Correct 683 ms 640 KB Output is correct
16 Correct 507 ms 768 KB Output is correct
17 Correct 633 ms 652 KB Output is correct
18 Correct 602 ms 892 KB Output is correct
19 Correct 607 ms 1008 KB Output is correct
20 Correct 480 ms 828 KB Output is correct
21 Correct 59 ms 640 KB Output is correct
22 Correct 68 ms 768 KB Output is correct
23 Correct 130 ms 812 KB Output is correct
24 Correct 6 ms 648 KB Output is correct
25 Correct 5 ms 652 KB Output is correct
26 Correct 4 ms 640 KB Output is correct
27 Correct 4 ms 644 KB Output is correct
28 Correct 2 ms 652 KB Output is correct
29 Correct 596 ms 656 KB Output is correct
30 Correct 576 ms 644 KB Output is correct
31 Correct 504 ms 640 KB Output is correct
32 Correct 624 ms 776 KB Output is correct
33 Correct 531 ms 644 KB Output is correct
34 Correct 365 ms 1024 KB Output is correct
35 Correct 531 ms 1024 KB Output is correct
36 Correct 523 ms 1280 KB Output is correct
37 Correct 536 ms 1140 KB Output is correct
38 Correct 506 ms 1132 KB Output is correct
39 Correct 507 ms 768 KB Output is correct
40 Correct 537 ms 1024 KB Output is correct
41 Correct 553 ms 788 KB Output is correct
42 Correct 85 ms 828 KB Output is correct
43 Correct 149 ms 768 KB Output is correct
44 Correct 171 ms 800 KB Output is correct
45 Correct 176 ms 768 KB Output is correct
46 Correct 333 ms 768 KB Output is correct
47 Correct 339 ms 780 KB Output is correct
48 Correct 70 ms 768 KB Output is correct
49 Correct 79 ms 1024 KB Output is correct