oj.uz

Submission #1073798

# Submission time Handle Problem Language Result Execution time Memory
1073798 2024-08-24T21:34:36 Z thatsgonzalez Stations (IOI20_stations) C++14
69.868 / 100
 656 ms 1636 KB 
#include "stations.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;


#define pb push_back

int mn = 0;
map<int,bool> mp;

int dfs(int node, int p, vector<vector<int>> &g, vector<int> &sub_tree){

	for(auto &x: g[node]){
		if(x == p) continue;

		sub_tree[node]+=dfs(x,node,g,sub_tree);

	}

	return sub_tree[node]=sub_tree[node]+1;

}

void calc_labels(int node, int p, int t, vector<vector<int>> &g, vector<int> &sub_tree, vector<int> &labels){
	if(!t){
		while(mp[mn]) mn++;
		mp[mn] = 1;
		labels[node] = mn; 
		while(mp[mn]) mn++;
	}
	for(auto &x: g[node]){
		if(x == p) continue;
		int turno = t^1;
		calc_labels(x,node,turno,g,sub_tree,labels);
	}
	if(t){
		while(mp[mn]) mn++;
		mp[mn] = 1;
		labels[node] = mn; 
		while(mp[mn]) mn++;
	}

}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	
	vector<int> sub_tree(n,0);
	vector<vector<int>> g(n);
	vector<int> labels(n);

	for(int i = 0; i<n-1; i++){
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}


	dfs(0,-1,g,sub_tree);
	calc_labels(0,-1,1,g,sub_tree,labels);


	return labels;
}

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

}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 1196 KB Output is correct
2 Correct 281 ms 1432 KB Output is correct
3 Correct 627 ms 684 KB Output is correct
4 Correct 470 ms 684 KB Output is correct
5 Correct 445 ms 684 KB Output is correct
6 Correct 293 ms 1452 KB Output is correct
7 Correct 308 ms 940 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 772 KB Output is correct
11 Correct 420 ms 684 KB Output is correct
12 Correct 368 ms 1284 KB Output is correct
13 Correct 326 ms 1448 KB Output is correct
14 Correct 326 ms 684 KB Output is correct
15 Correct 34 ms 768 KB Output is correct
16 Correct 38 ms 1004 KB Output is correct
17 Correct 56 ms 1200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 684 KB Output is correct
2 Correct 451 ms 684 KB Output is correct
3 Correct 392 ms 684 KB Output is correct
4 Correct 1 ms 772 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 408 ms 684 KB Output is correct
8 Correct 656 ms 684 KB Output is correct
9 Correct 482 ms 684 KB Output is correct
10 Correct 400 ms 944 KB Output is correct
11 Correct 2 ms 1272 KB Output is correct
12 Correct 3 ms 776 KB Output is correct
13 Correct 2 ms 776 KB Output is correct
14 Correct 2 ms 828 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 323 ms 772 KB Output is correct
17 Correct 373 ms 684 KB Output is correct
18 Correct 342 ms 684 KB Output is correct
19 Correct 356 ms 684 KB Output is correct
20 Correct 384 ms 936 KB Output is correct

Subtask #5
43.868 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 380 ms 1196 KB Partially correct
2 Partially correct 331 ms 1192 KB Partially correct
3 Correct 557 ms 684 KB Output is correct
4 Correct 488 ms 684 KB Output is correct
5 Correct 415 ms 684 KB Output is correct
6 Partially correct 310 ms 1196 KB Partially correct
7 Correct 318 ms 940 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 768 KB Output is correct
11 Partially correct 370 ms 1196 KB Partially correct
12 Partially correct 351 ms 940 KB Partially correct
13 Correct 634 ms 684 KB Output is correct
14 Correct 450 ms 684 KB Output is correct
15 Correct 396 ms 684 KB Output is correct
16 Correct 313 ms 684 KB Output is correct
17 Correct 434 ms 684 KB Output is correct
18 Partially correct 312 ms 1276 KB Partially correct
19 Partially correct 301 ms 1272 KB Partially correct
20 Correct 358 ms 684 KB Output is correct
21 Correct 38 ms 684 KB Output is correct
22 Partially correct 47 ms 996 KB Partially correct
23 Partially correct 61 ms 1192 KB Partially correct
24 Correct 4 ms 768 KB Output is correct
25 Correct 3 ms 768 KB Output is correct
26 Correct 3 ms 768 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 0 ms 768 KB Output is correct
29 Correct 335 ms 688 KB Output is correct
30 Correct 376 ms 684 KB Output is correct
31 Correct 361 ms 684 KB Output is correct
32 Correct 355 ms 684 KB Output is correct
33 Correct 361 ms 684 KB Output is correct
34 Partially correct 215 ms 1196 KB Partially correct
35 Partially correct 297 ms 1292 KB Partially correct
36 Partially correct 306 ms 1444 KB Partially correct
37 Partially correct 295 ms 1440 KB Partially correct
38 Partially correct 302 ms 1272 KB Partially correct
39 Partially correct 326 ms 1276 KB Partially correct
40 Partially correct 308 ms 1528 KB Partially correct
41 Partially correct 296 ms 1636 KB Partially correct
42 Partially correct 39 ms 972 KB Partially correct
43 Partially correct 60 ms 1224 KB Partially correct
44 Partially correct 96 ms 1176 KB Partially correct
45 Partially correct 112 ms 1196 KB Partially correct
46 Partially correct 233 ms 1196 KB Partially correct
47 Partially correct 201 ms 1196 KB Partially correct
48 Partially correct 39 ms 1172 KB Partially correct
49 Partially correct 31 ms 1260 KB Partially correct