oj.uz

Submission #985411

# Submission time Handle Problem Language Result Execution time Memory
985411 2024-05-17T18:55:01 Z FZ_Melo Stations (IOI20_stations) C++14
52.3244 / 100
 634 ms 1476 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj;
int tam[1001];

void dfs(int node, int ant, vector<int> &labels, int &num){
	labels[node]=num;
	num++;
	tam[node]=0;
	for(int h: adj[node]){
		if(h==ant)
			continue;
		dfs(h, node, labels, num);
		tam[node]+=tam[h]+1;
	}
	labels[node]*=1000;
	labels[node]+=tam[node];
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<int> labels(n);
	adj.clear();
	adj.resize(n+1);
	int num=0;
	for(int i=0; i<n-1; i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(0, 0, labels, num);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int x=s/1000;
	int sub=s-(x*1000);
	if(t/1000>x+sub || t/1000<x){
		for(int i=0; i<c.size(); i++){
			if(x>c[i]/1000)
				return c[i];
		}
	}
	else{
		for(int i=0; i<c.size(); i++){
			if(c[i]/1000<x || c[i]/1000>t/1000)
				continue;
			int id=c[i]/1000;
			int cnt=c[i]-(id*1000);
			if(t/1000<=id+cnt)
				return c[i];
		}
	}
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 984 KB Output is correct
2 Correct 326 ms 1224 KB Output is correct
3 Correct 601 ms 684 KB Output is correct
4 Correct 412 ms 684 KB Output is correct
5 Correct 410 ms 684 KB Output is correct
6 Correct 282 ms 944 KB Output is correct
7 Correct 300 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 374 ms 684 KB Output is correct
12 Correct 329 ms 1032 KB Output is correct
13 Correct 317 ms 1276 KB Output is correct
14 Correct 296 ms 684 KB Output is correct
15 Correct 29 ms 768 KB Output is correct
16 Correct 40 ms 908 KB Output is correct
17 Correct 66 ms 868 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 688 KB Output is correct
2 Correct 426 ms 684 KB Output is correct
3 Correct 384 ms 688 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 0 ms 764 KB Output is correct
7 Correct 393 ms 684 KB Output is correct
8 Correct 552 ms 940 KB Output is correct
9 Correct 434 ms 684 KB Output is correct
10 Correct 417 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 344 ms 716 KB Output is correct
17 Correct 297 ms 684 KB Output is correct
18 Correct 338 ms 684 KB Output is correct
19 Correct 328 ms 684 KB Output is correct
20 Correct 322 ms 684 KB Output is correct

Subtask #5
26.3244 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 331 ms 1000 KB Partially correct
2 Partially correct 287 ms 960 KB Partially correct
3 Correct 578 ms 684 KB Output is correct
4 Partially correct 414 ms 936 KB Partially correct
5 Partially correct 374 ms 684 KB Partially correct
6 Partially correct 280 ms 952 KB Partially correct
7 Partially correct 289 ms 684 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 2 ms 768 KB Partially correct
10 Partially correct 1 ms 768 KB Partially correct
11 Partially correct 313 ms 904 KB Partially correct
12 Partially correct 338 ms 824 KB Partially correct
13 Correct 634 ms 684 KB Output is correct
14 Partially correct 409 ms 684 KB Partially correct
15 Partially correct 371 ms 684 KB Partially correct
16 Partially correct 288 ms 684 KB Partially correct
17 Partially correct 377 ms 684 KB Partially correct
18 Partially correct 294 ms 1260 KB Partially correct
19 Partially correct 342 ms 1288 KB Partially correct
20 Partially correct 283 ms 684 KB Partially correct
21 Partially correct 37 ms 768 KB Partially correct
22 Partially correct 43 ms 884 KB Partially correct
23 Partially correct 62 ms 1204 KB Partially correct
24 Partially correct 4 ms 768 KB Partially correct
25 Partially correct 3 ms 760 KB Partially correct
26 Partially correct 3 ms 764 KB Partially correct
27 Partially correct 3 ms 768 KB Partially correct
28 Partially correct 0 ms 768 KB Partially correct
29 Partially correct 355 ms 936 KB Partially correct
30 Partially correct 324 ms 940 KB Partially correct
31 Partially correct 291 ms 684 KB Partially correct
32 Partially correct 326 ms 860 KB Partially correct
33 Partially correct 342 ms 684 KB Partially correct
34 Partially correct 233 ms 976 KB Partially correct
35 Partially correct 319 ms 1476 KB Partially correct
36 Partially correct 316 ms 1068 KB Partially correct
37 Partially correct 298 ms 1268 KB Partially correct
38 Partially correct 312 ms 1176 KB Partially correct
39 Partially correct 287 ms 1188 KB Partially correct
40 Partially correct 313 ms 1188 KB Partially correct
41 Partially correct 276 ms 1140 KB Partially correct
42 Partially correct 39 ms 1180 KB Partially correct
43 Partially correct 63 ms 908 KB Partially correct
44 Partially correct 94 ms 872 KB Partially correct
45 Partially correct 104 ms 876 KB Partially correct
46 Partially correct 204 ms 864 KB Partially correct
47 Partially correct 231 ms 904 KB Partially correct
48 Partially correct 45 ms 1144 KB Partially correct
49 Partially correct 39 ms 1260 KB Partially correct