oj.uz

Submission #320465

# Submission time Handle Problem Language Result Execution time Memory
320465 2020-11-08T20:04:44 Z nikatamliani Stations (IOI20_stations) C++14
100 / 100
 1097 ms 1324 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
void dfs(int x, int p, vector < vector < int > > &adj, vector < int > &labels, int depth) {
	static int timer = -1;
	++timer;
	if(depth) labels[x] = timer;
	for(int to : adj[x]) {
		if(to != p) {
			dfs(to, x, adj, labels, depth ^ 1);
		}
	}
	++timer;
	if(!depth) labels[x] = timer;
}
vector < int > label(int n, int k, vector < int > u, vector < int > v) {
	vector < int > labels(n);
	vector< vector < int > > adj(n, vector < int >());
	for(int i = 0; i < n - 1; ++i) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(0, -1, adj, labels, 0);
	vector < vector < int > > g;
	for(int i = 0; i < n; ++i) {
	    g.push_back({labels[i], i});
	}
	sort(g.begin(), g.end());
	for(int i = 0; i < n; ++i) {
	    labels[g[i][1]] = i;
	}
	return labels;
}

int find_next_station(int s, int t, vector < int > c) {
    if(c.size() == 1) return c[0];
	sort(c.begin(), c.end());
	if(s == 0) {
	    int my_in = 0;
	    int my_out = c.back();
	    for(int i = 0; i < c.size(); ++i) {
	        int cur_in, cur_out;
	        if(i == 0) {
	            cur_in = my_in;
	        } else {
	            cur_in = c[i - 1] + 1;
	        }
	        cur_out = c[i];
	        if(cur_in <= t && t <= cur_out) {
	            return c[i];
	        }
	    }
	} else {
	    int my_in = -1, my_out = -1;
	    if(s < c[0]) {
	        my_in = s;
	        my_out = c[(int)c.size() - 2];
	        for(int i = 0; i < (int)c.size() - 1; ++i) {
	            int cur_in, cur_out;
	            cur_out = c[i];
	            if(i == 0) {
	                cur_in = my_in;
	            } else {
	                cur_in = c[i - 1] + 1; 
	            }
	            if(cur_in <= t && t <= cur_out) return c[i];
	        }
	        return c.back();
	    } else {
	        my_in = c[1];
	        my_out = s;
	        for(int i = 1; i < (int)c.size(); ++i) {
	            int cur_in, cur_out;
	            cur_in = c[i];
	            if(i == (int)c.size() - 1) {
	                cur_out = s;
	            } else {
	                cur_out = c[i + 1] - 1;
	            }
	            if(cur_in <= t && t <= cur_out) return c[i];
	        }
	        return c[0];
	    }
	}
}
// int main() {
//     vector < int > x = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
//     // for(int i : x) cout << i << ' ';
//     cout << find_next_station(3, 9, {5}) << '\n';  
// }

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |      for(int i = 0; i < c.size(); ++i) {
      |                     ~~^~~~~~~~~~
stations.cpp:40:10: warning: unused variable 'my_out' [-Wunused-variable]
   40 |      int my_out = c.back();
      |          ^~~~~~
stations.cpp:54:22: warning: variable 'my_out' set but not used [-Wunused-but-set-variable]
   54 |      int my_in = -1, my_out = -1;
      |                      ^~~~~~
stations.cpp:85:1: warning: control reaches end of non-void function [-Wreturn-type]
   85 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 864 KB Output is correct
2 Correct 521 ms 860 KB Output is correct
3 Correct 1097 ms 884 KB Output is correct
4 Correct 650 ms 868 KB Output is correct
5 Correct 604 ms 660 KB Output is correct
6 Correct 517 ms 904 KB Output is correct
7 Correct 613 ms 928 KB Output is correct
8 Correct 3 ms 904 KB Output is correct
9 Correct 4 ms 736 KB Output is correct
10 Correct 1 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 884 KB Output is correct
2 Correct 561 ms 984 KB Output is correct
3 Correct 961 ms 860 KB Output is correct
4 Correct 764 ms 892 KB Output is correct
5 Correct 601 ms 756 KB Output is correct
6 Correct 488 ms 884 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 884 KB Output is correct
2 Correct 529 ms 864 KB Output is correct
3 Correct 1087 ms 756 KB Output is correct
4 Correct 728 ms 756 KB Output is correct
5 Correct 649 ms 756 KB Output is correct
6 Correct 459 ms 896 KB Output is correct
7 Correct 454 ms 1068 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 6 ms 884 KB Output is correct
10 Correct 2 ms 756 KB Output is correct
11 Correct 623 ms 748 KB Output is correct
12 Correct 534 ms 984 KB Output is correct
13 Correct 450 ms 932 KB Output is correct
14 Correct 450 ms 864 KB Output is correct
15 Correct 58 ms 756 KB Output is correct
16 Correct 84 ms 756 KB Output is correct
17 Correct 147 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 660 KB Output is correct
2 Correct 656 ms 736 KB Output is correct
3 Correct 579 ms 868 KB Output is correct
4 Correct 3 ms 916 KB Output is correct
5 Correct 3 ms 736 KB Output is correct
6 Correct 0 ms 736 KB Output is correct
7 Correct 554 ms 756 KB Output is correct
8 Correct 871 ms 992 KB Output is correct
9 Correct 661 ms 736 KB Output is correct
10 Correct 594 ms 864 KB Output is correct
11 Correct 4 ms 1012 KB Output is correct
12 Correct 5 ms 736 KB Output is correct
13 Correct 4 ms 736 KB Output is correct
14 Correct 4 ms 736 KB Output is correct
15 Correct 2 ms 876 KB Output is correct
16 Correct 499 ms 736 KB Output is correct
17 Correct 515 ms 872 KB Output is correct
18 Correct 504 ms 756 KB Output is correct
19 Correct 515 ms 864 KB Output is correct
20 Correct 484 ms 864 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 896 KB Output is correct
2 Correct 453 ms 864 KB Output is correct
3 Correct 930 ms 864 KB Output is correct
4 Correct 865 ms 756 KB Output is correct
5 Correct 742 ms 868 KB Output is correct
6 Correct 480 ms 904 KB Output is correct
7 Correct 581 ms 956 KB Output is correct
8 Correct 2 ms 1012 KB Output is correct
9 Correct 4 ms 756 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 542 ms 884 KB Output is correct
12 Correct 539 ms 864 KB Output is correct
13 Correct 892 ms 756 KB Output is correct
14 Correct 710 ms 756 KB Output is correct
15 Correct 758 ms 736 KB Output is correct
16 Correct 553 ms 1012 KB Output is correct
17 Correct 590 ms 864 KB Output is correct
18 Correct 549 ms 1012 KB Output is correct
19 Correct 494 ms 1000 KB Output is correct
20 Correct 412 ms 992 KB Output is correct
21 Correct 60 ms 756 KB Output is correct
22 Correct 71 ms 796 KB Output is correct
23 Correct 119 ms 976 KB Output is correct
24 Correct 7 ms 788 KB Output is correct
25 Correct 6 ms 736 KB Output is correct
26 Correct 5 ms 736 KB Output is correct
27 Correct 4 ms 864 KB Output is correct
28 Correct 2 ms 556 KB Output is correct
29 Correct 505 ms 768 KB Output is correct
30 Correct 775 ms 1032 KB Output is correct
31 Correct 514 ms 900 KB Output is correct
32 Correct 555 ms 864 KB Output is correct
33 Correct 565 ms 872 KB Output is correct
34 Correct 309 ms 884 KB Output is correct
35 Correct 417 ms 1044 KB Output is correct
36 Correct 426 ms 1324 KB Output is correct
37 Correct 571 ms 1272 KB Output is correct
38 Correct 435 ms 792 KB Output is correct
39 Correct 592 ms 1056 KB Output is correct
40 Correct 421 ms 940 KB Output is correct
41 Correct 518 ms 1176 KB Output is correct
42 Correct 68 ms 996 KB Output is correct
43 Correct 148 ms 864 KB Output is correct
44 Correct 146 ms 1244 KB Output is correct
45 Correct 198 ms 928 KB Output is correct
46 Correct 442 ms 884 KB Output is correct
47 Correct 353 ms 1052 KB Output is correct
48 Correct 60 ms 864 KB Output is correct
49 Correct 66 ms 992 KB Output is correct