oj.uz

Submission #410516

# Submission time Handle Problem Language Result Execution time Memory
410516 2021-05-22T21:00:03 Z 534351 Stations (IOI20_stations) C++17
10 / 100
 1004 ms 900 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()

const int MAXN = 1013;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, K, T;
vi edge[MAXN];
int st[MAXN], ft[MAXN];
vi ans;
//inside each vtx, we store start time and finish time.

void dfs(int u, int p)
{
	st[u] = T;
	ft[u] = T;
	T++;
	for (int v : edge[u])
	{
		if (v == p) continue;
		dfs(v, u);
		ft[u] = ft[v];
	}
}

vi label(int n, int k, vi U, vi V)
{
	N = n; K = k;
	FOR(i, 0, N)
	{
		edge[i].clear();
	}
	ans.clear();
	FOR(i, 0, N - 1)
	{
		int u = U[i], v = V[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
	dfs(0, N);
	ans.resize(N);
	FOR(i, 0, N)
	{
		ans[i] = st[i] * 1000 + ft[i];
	}
	return ans;
}

int find_next_station(int s, int t, vi ch)
{
	//you're at s and you want to go to t.
	int stu = s / 1000, ftu = s % 1000;
	int stv = t / 1000, ftv = t % 1000;
	if (stu <= stv && stv <= ftu)
	{
		for (int x : ch)
		{
			int stx = x / 1000, ftx = x % 1000;
			if (stx < stu) continue;
			if (stx <= stv && stv <= ftx)
			{
				return x;
			}
		}
	}
	for (int x : ch)
	{
		int stx = x / 1000, ftx = x % 1000;
		if (stx < stu) return x;
	}
	assert(false);
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, vi)':
stations.cpp:101:23: warning: unused variable 'ftx' [-Wunused-variable]
  101 |   int stx = x / 1000, ftx = x % 1000;
      |                       ^~~
stations.cpp:86:22: warning: unused variable 'ftv' [-Wunused-variable]
   86 |  int stv = t / 1000, ftv = t % 1000;
      |                      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 452 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 5 ms 308 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 4 ms 444 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 982 ms 400 KB Output is correct
2 Correct 885 ms 400 KB Output is correct
3 Correct 806 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 710 ms 528 KB Output is correct
8 Correct 1004 ms 400 KB Output is correct
9 Correct 827 ms 588 KB Output is correct
10 Correct 616 ms 400 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 7 ms 464 KB Output is correct
13 Correct 5 ms 476 KB Output is correct
14 Correct 5 ms 580 KB Output is correct
15 Correct 2 ms 608 KB Output is correct
16 Correct 506 ms 516 KB Output is correct
17 Correct 578 ms 400 KB Output is correct
18 Correct 576 ms 504 KB Output is correct
19 Correct 569 ms 532 KB Output is correct
20 Correct 569 ms 516 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 900 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -