oj.uz

Submission #1073734

# Submission time Handle Problem Language Result Execution time Memory
1073734 2024-08-24T19:31:58 Z allin27x Stations (IOI20_stations) C++17
10 / 100
 594 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;
#include "stations.h"

const int N = 1001;
vector<int> adj[N];
int tin[N];
int tout[N];
int tp = 0;

void dfs(int i, int p) {
	tin[i] = tp++;
	for (int c: adj[i]) {
		if (c == p) continue;
		dfs(c,i);
	}
	tout[i] = tp;
}

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

int find_next_station(int s, int t, std::vector<int> c) {
	int s_in = s/1000; int s_out = s%1000;
	int t_in = t/1000; int t_out = t%1000;
	if (s_in <= t_in && t_out <= s_out) {
		// t is below s
		for (int x: c) {
			int x_in = x/1000; int x_out = x%1000;
			if (x_in < s_in) continue;
			if (x_in <= t_in && t_out <= x_out) return x;
		}
	} else {
		for (int x: c) {
			if (x/1000 < s_in) return x;
		}
	}
	return -1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 684 KB Output is correct
2 Correct 493 ms 684 KB Output is correct
3 Correct 399 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 764 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 436 ms 684 KB Output is correct
8 Correct 594 ms 684 KB Output is correct
9 Correct 476 ms 680 KB Output is correct
10 Correct 409 ms 684 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 358 ms 684 KB Output is correct
17 Correct 368 ms 684 KB Output is correct
18 Correct 321 ms 684 KB Output is correct
19 Correct 348 ms 684 KB Output is correct
20 Correct 366 ms 684 KB Output is correct

Subtask #5
0 / 61.0

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