oj.uz

Submission #927017

# Submission time Handle Problem Language Result Execution time Memory
927017 2024-02-14T06:52:24 Z ByeWorld Stations (IOI20_stations) C++14
10 / 100
 560 ms 992 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 = 10;

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 632 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=0, label=9970
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 992 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 684 KB Output is correct
2 Correct 431 ms 684 KB Output is correct
3 Correct 390 ms 684 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 376 ms 684 KB Output is correct
8 Correct 515 ms 944 KB Output is correct
9 Correct 432 ms 684 KB Output is correct
10 Correct 350 ms 684 KB Output is correct
11 Correct 3 ms 884 KB Output is correct
12 Correct 3 ms 764 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 3 ms 764 KB Output is correct
15 Correct 0 ms 764 KB Output is correct
16 Correct 318 ms 684 KB Output is correct
17 Correct 310 ms 684 KB Output is correct
18 Correct 351 ms 880 KB Output is correct
19 Correct 348 ms 684 KB Output is correct
20 Correct 284 ms 684 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 980 KB Wrong query response.
2 Halted 0 ms 0 KB -