oj.uz

Submission #308156

# Submission time Handle Problem Language Result Execution time Memory
308156 2020-09-30T06:48:33 Z jwvg0425 Stations (IOI20_stations) C++17
10 / 100
 899 ms 1024 KB 
#include "stations.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

struct Solver
{
	vector<int> edge[1005];
	int in[1005] = { 0, }, out[1005] = { 0, };
	int vis = 0;

	void dfs(int root)
	{
		in[root] = vis;
		vis++;

		for (auto& e : edge[root])
		{
			edge[e].erase(find(all(edge[e]), root));
			dfs(e);
		}

		out[root] = vis;
	}
};

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	Solver s;
	for (int i = 0; i < n - 1; i++)
	{
		s.edge[u[i]].push_back(v[i]);
		s.edge[v[i]].push_back(u[i]);
	}

	s.dfs(0);

	vector<int> res(n);
	for (int i = 0; i < n; i++)
		res[i] = s.in[i] * 1000 + s.out[i];

	return res;
}

int find_next_station(int s, int t, vector<int> c)
{
	int ti = t / 1000;
	int to = t % 1000;
	int si = s / 1000;
	int so = s % 1000;
	int p = c[0];

	for (auto& e : c)
	{
		int ei = e / 1000;
		int eo = e % 1000;

		if (ei <= si && eo >= so)
		{
			p = e;
			continue;
		}

		if (ei <= ti && eo >= to)
			return e;
	}

	return p;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 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 6 ms 384 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 523 ms 1024 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 864 KB Output is correct
2 Correct 678 ms 872 KB Output is correct
3 Correct 645 ms 872 KB Output is correct
4 Correct 3 ms 884 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 0 ms 876 KB Output is correct
7 Correct 578 ms 768 KB Output is correct
8 Correct 898 ms 864 KB Output is correct
9 Correct 709 ms 868 KB Output is correct
10 Correct 603 ms 876 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 6 ms 896 KB Output is correct
13 Correct 5 ms 872 KB Output is correct
14 Correct 4 ms 1000 KB Output is correct
15 Correct 2 ms 884 KB Output is correct
16 Correct 521 ms 768 KB Output is correct
17 Correct 494 ms 768 KB Output is correct
18 Correct 494 ms 780 KB Output is correct
19 Correct 498 ms 768 KB Output is correct
20 Correct 486 ms 872 KB Output is correct

Subtask #5
0 / 61.0

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