oj.uz

Submission #961314

# Submission time Handle Problem Language Result Execution time Memory
961314 2024-04-11T19:59:04 Z Macker Stations (IOI20_stations) C++17
10 / 100
 600 ms 1120 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

vector<int> in, out;
vector<vector<int>> adj;
int tim = 0;

void dfs(int a, int p){
	in[a] = tim++;
	for (auto b : adj[a]){
		if(b != p) dfs(b, a);
	}
	out[a] = tim-1;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	adj.assign(n, {});
	in = out = vector<int>(n);
	FOR(i, n-1){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(0, 0);
	FOR(i, n){
		labels[i] = out[i] + 1000*in[i];
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int ins = s/1000;
	int outs = s%1000;
	int it = t/1000;
	if(ins <= it && outs >= it){
		for (auto i : c) {
			int ii = i/1000;
			int oi = i%1000;
			if(ii > ins && ii <= it && oi >= it) return i;
		}
	}
	else{
		for (auto i : c) {
			if(i / 1000 < ins) return i;	
		}
	}
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 684 KB Output is correct
2 Correct 408 ms 684 KB Output is correct
3 Correct 400 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 392 ms 688 KB Output is correct
8 Correct 590 ms 684 KB Output is correct
9 Correct 453 ms 684 KB Output is correct
10 Correct 356 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 0 ms 764 KB Output is correct
16 Correct 351 ms 684 KB Output is correct
17 Correct 322 ms 684 KB Output is correct
18 Correct 350 ms 684 KB Output is correct
19 Correct 328 ms 684 KB Output is correct
20 Correct 344 ms 684 KB Output is correct

Subtask #5
0 / 61.0

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