oj.uz

Submission #927019

# Submission time Handle Problem Language Result Execution time Memory
927019 2024-02-14T06:53:46 Z ByeWorld Stations (IOI20_stations) C++14
52.3205 / 100
 585 ms 1548 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int MAXN = 1e3+10;
const int MAX = 1e3;

int n, k;
vector <int> adj[MAXN], dw[MAXN];
vector <int> lab;
int chi[MAXN], val[MAXN], cnt;

void dfs(int nw, int par){ // build val, tergantung dfs
	val[nw] = cnt++;
	for(auto nx : adj[nw]){
		if(nx == par) continue;
		dw[nw].pb(nx);
		dfs(nx, nw);
	}
}
void bd(int nw){
	chi[nw] = val[nw];
	for(auto nx : dw[nw]){
		bd(nx);
		chi[nw] = max(chi[nw], chi[nx]);
	}
}

vector<int> label(int N, int K, vector<int> u, vector<int> v) {
	n = N; k = K;
	lab.clear(); lab.resize(n); cnt = 0;
	for(int i=0; i<=n; i++){
		adj[i].clear(); dw[i].clear();
		chi[i] = -1; val[i] = 0;
	}

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

	dfs(0, -1); bd(0);
	for(int i=0; i<n; i++){
		lab[i] = val[i] + chi[i]*MAX;
	}
	//for(int i=0; i<n; i++) cout << i << ' ' << val[i] << ' ' << chi[i] << ' '<< lab[i] << " p\n";
		
	return lab;
}

int find_next_station(int s, int t, vector<int> c) { // c sorted
	//cout << s << ' ' << t << " pp\n";
	int num = c.size();
	vector <pii> val(num);
	for(int i=0; i<c.size(); i++){
		val[i].fi = c[i]%MAX; val[i].se = c[i] / MAX;
		// idx, max idx di subtree
	}
	sort(val.begin(), val.end()); // based on idx
	//for(auto in : val) cout << in.fi << ' '<< in.se << " xx\n";

	int valt = t%MAX, idx = -1;
	if((s%MAX) ==0){ // s itu root
		for(int i=0; i<val.size(); i++){
			if(val[i].fi <= valt){
				idx = i;
			}
		}
		return (val[idx].fi + val[idx].se*MAX);
	}

	int mx = s/MAX; // kalo nx==0, brati gk ada nx
	for(int i=0; i<val.size(); i++){
		if(val[i].fi <= valt){
			idx = i;
		}
	}

	if(valt < (s%MAX) || valt > mx) idx = 0; // parent
	return (val[idx].fi + val[idx].se*MAX);
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 984 KB Output is correct
2 Correct 295 ms 984 KB Output is correct
3 Correct 570 ms 684 KB Output is correct
4 Correct 385 ms 684 KB Output is correct
5 Correct 439 ms 684 KB Output is correct
6 Correct 252 ms 976 KB Output is correct
7 Correct 268 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 Correct 395 ms 688 KB Output is correct
12 Correct 316 ms 1116 KB Output is correct
13 Correct 341 ms 1140 KB Output is correct
14 Correct 314 ms 684 KB Output is correct
15 Correct 42 ms 768 KB Output is correct
16 Correct 42 ms 964 KB Output is correct
17 Correct 64 ms 916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 684 KB Output is correct
2 Correct 434 ms 684 KB Output is correct
3 Correct 372 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 371 ms 820 KB Output is correct
8 Correct 516 ms 684 KB Output is correct
9 Correct 390 ms 940 KB Output is correct
10 Correct 343 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 376 ms 684 KB Output is correct
17 Correct 319 ms 684 KB Output is correct
18 Correct 295 ms 684 KB Output is correct
19 Correct 303 ms 684 KB Output is correct
20 Correct 368 ms 684 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 327 ms 988 KB Partially correct
2 Partially correct 303 ms 972 KB Partially correct
3 Partially correct 585 ms 684 KB Partially correct
4 Partially correct 428 ms 684 KB Partially correct
5 Partially correct 409 ms 1120 KB Partially correct
6 Partially correct 289 ms 984 KB Partially correct
7 Partially correct 334 ms 940 KB Partially correct
8 Partially correct 1 ms 768 KB Partially correct
9 Partially correct 3 ms 768 KB Partially correct
10 Partially correct 1 ms 768 KB Partially correct
11 Partially correct 266 ms 912 KB Partially correct
12 Partially correct 297 ms 880 KB Partially correct
13 Partially correct 559 ms 684 KB Partially correct
14 Partially correct 458 ms 684 KB Partially correct
15 Partially correct 341 ms 688 KB Partially correct
16 Partially correct 302 ms 684 KB Partially correct
17 Partially correct 370 ms 684 KB Partially correct
18 Partially correct 287 ms 1228 KB Partially correct
19 Partially correct 307 ms 1132 KB Partially correct
20 Partially correct 255 ms 684 KB Partially correct
21 Partially correct 41 ms 716 KB Partially correct
22 Partially correct 41 ms 956 KB Partially correct
23 Partially correct 60 ms 1220 KB Partially correct
24 Partially correct 3 ms 768 KB Partially correct
25 Partially correct 3 ms 884 KB Partially correct
26 Partially correct 3 ms 1016 KB Partially correct
27 Partially correct 1 ms 764 KB Partially correct
28 Partially correct 2 ms 768 KB Partially correct
29 Partially correct 372 ms 944 KB Partially correct
30 Partially correct 333 ms 684 KB Partially correct
31 Partially correct 313 ms 684 KB Partially correct
32 Partially correct 319 ms 684 KB Partially correct
33 Partially correct 321 ms 684 KB Partially correct
34 Partially correct 181 ms 980 KB Partially correct
35 Partially correct 273 ms 1400 KB Partially correct
36 Partially correct 256 ms 1248 KB Partially correct
37 Partially correct 301 ms 1232 KB Partially correct
38 Partially correct 265 ms 1360 KB Partially correct
39 Partially correct 305 ms 1212 KB Partially correct
40 Partially correct 282 ms 1116 KB Partially correct
41 Partially correct 296 ms 1372 KB Partially correct
42 Partially correct 37 ms 1204 KB Partially correct
43 Partially correct 61 ms 976 KB Partially correct
44 Partially correct 86 ms 964 KB Partially correct
45 Partially correct 93 ms 968 KB Partially correct
46 Partially correct 177 ms 912 KB Partially correct
47 Partially correct 171 ms 952 KB Partially correct
48 Partially correct 40 ms 1548 KB Partially correct
49 Partially correct 39 ms 1296 KB Partially correct