oj.uz

Submission #320463

# Submission time Handle Problem Language Result Execution time Memory
320463 2020-11-08T19:56:07 Z nikatamliani Stations (IOI20_stations) C++14
67.2267 / 100
 1043 ms 1168 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
void dfs(int x, int p, vector < vector < int > > &adj, vector < int > &in, vector < int > &out, vector < int > &labels, int depth) {
	static int timer = -1;
	in[x] = ++timer;
	for(int to : adj[x]) {
		if(to != p) {
			dfs(to, x, adj, in, out, labels, depth ^ 1);
		}
	}
	out[x] = ++timer;
	if(depth) {
		labels[x] = in[x];
	} else {
		labels[x] = out[x];  
	}
}
vector < int > label(int n, int k, vector < int > u, vector < int > v) {
	vector < int > labels(n), in(n), out(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, in, out, labels, 0);
// 	vector < vector < int > > g;
// 	for(int i = 0; i < n; ++i) {
// 		g.push_back({in[i], i, 1});
// 		g.push_back({out[i], i, 2});
// 	}
// 	sort(g.begin(), g.end());
// 	for(int cnt = -1, i = 0; i < g.size(); ++i) {
// 		if(i == 0 || g[i][0] != g[i - 1][0]) ++cnt;
// 		if(g[i][2] == 1) in[g[i][1]] = cnt;
// 		if(g[i][2] == 2) out[g[i][1]] = cnt;
// 	}
	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:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |      for(int i = 0; i < c.size(); ++i) {
      |                     ~~^~~~~~~~~~
stations.cpp:46:10: warning: unused variable 'my_out' [-Wunused-variable]
   46 |      int my_out = c.back();
      |          ^~~~~~
stations.cpp:60:22: warning: variable 'my_out' set but not used [-Wunused-but-set-variable]
   60 |      int my_in = -1, my_out = -1;
      |                      ^~~~~~
stations.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
   91 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 492 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=0, label=2021
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 364 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1991
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 864 KB Output is correct
2 Correct 455 ms 884 KB Output is correct
3 Correct 1043 ms 688 KB Output is correct
4 Correct 659 ms 864 KB Output is correct
5 Correct 576 ms 756 KB Output is correct
6 Correct 453 ms 912 KB Output is correct
7 Correct 452 ms 948 KB Output is correct
8 Correct 3 ms 1012 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 1 ms 756 KB Output is correct
11 Correct 540 ms 756 KB Output is correct
12 Correct 454 ms 1148 KB Output is correct
13 Correct 506 ms 1024 KB Output is correct
14 Correct 485 ms 1012 KB Output is correct
15 Correct 53 ms 908 KB Output is correct
16 Correct 70 ms 736 KB Output is correct
17 Correct 105 ms 756 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 928 KB Output is correct
2 Correct 639 ms 864 KB Output is correct
3 Correct 615 ms 860 KB Output is correct
4 Correct 3 ms 1140 KB Output is correct
5 Correct 4 ms 756 KB Output is correct
6 Correct 1 ms 872 KB Output is correct
7 Correct 611 ms 1012 KB Output is correct
8 Correct 856 ms 884 KB Output is correct
9 Correct 601 ms 864 KB Output is correct
10 Correct 549 ms 872 KB Output is correct
11 Correct 6 ms 756 KB Output is correct
12 Correct 6 ms 756 KB Output is correct
13 Correct 5 ms 756 KB Output is correct
14 Correct 4 ms 756 KB Output is correct
15 Correct 2 ms 896 KB Output is correct
16 Correct 513 ms 756 KB Output is correct
17 Correct 455 ms 1000 KB Output is correct
18 Correct 502 ms 868 KB Output is correct
19 Correct 475 ms 864 KB Output is correct
20 Correct 537 ms 1004 KB Output is correct

Subtask #5
41.2267 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 673 ms 920 KB Partially correct
2 Partially correct 463 ms 932 KB Partially correct
3 Correct 941 ms 872 KB Output is correct
4 Correct 740 ms 996 KB Output is correct
5 Correct 547 ms 1012 KB Output is correct
6 Partially correct 434 ms 1000 KB Partially correct
7 Partially correct 414 ms 1120 KB Partially correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 4 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Partially correct 468 ms 756 KB Partially correct
12 Partially correct 524 ms 772 KB Partially correct
13 Correct 906 ms 916 KB Output is correct
14 Correct 646 ms 864 KB Output is correct
15 Correct 619 ms 884 KB Output is correct
16 Partially correct 463 ms 1012 KB Partially correct
17 Correct 591 ms 896 KB Output is correct
18 Partially correct 468 ms 1168 KB Partially correct
19 Partially correct 449 ms 864 KB Partially correct
20 Partially correct 511 ms 780 KB Partially correct
21 Partially correct 58 ms 736 KB Partially correct
22 Partially correct 68 ms 736 KB Partially correct
23 Partially correct 114 ms 736 KB Partially correct
24 Correct 6 ms 736 KB Output is correct
25 Correct 6 ms 736 KB Output is correct
26 Correct 5 ms 876 KB Output is correct
27 Correct 4 ms 736 KB Output is correct
28 Correct 2 ms 756 KB Output is correct
29 Correct 525 ms 736 KB Output is correct
30 Correct 524 ms 760 KB Output is correct
31 Correct 525 ms 868 KB Output is correct
32 Correct 497 ms 736 KB Output is correct
33 Correct 527 ms 1012 KB Output is correct
34 Partially correct 325 ms 884 KB Partially correct
35 Partially correct 440 ms 1024 KB Partially correct
36 Partially correct 443 ms 884 KB Partially correct
37 Partially correct 469 ms 984 KB Partially correct
38 Partially correct 444 ms 1084 KB Partially correct
39 Partially correct 472 ms 880 KB Partially correct
40 Partially correct 466 ms 1084 KB Partially correct
41 Partially correct 514 ms 984 KB Partially correct
42 Partially correct 82 ms 756 KB Partially correct
43 Partially correct 111 ms 736 KB Partially correct
44 Partially correct 119 ms 736 KB Partially correct
45 Partially correct 144 ms 736 KB Partially correct
46 Partially correct 296 ms 756 KB Partially correct
47 Partially correct 393 ms 1140 KB Partially correct
48 Partially correct 76 ms 892 KB Partially correct
49 Partially correct 79 ms 864 KB Partially correct