oj.uz

Submission #308157

# Submission time Handle Problem Language Result Execution time Memory
308157 2020-09-30T06:50:26 Z jwvg0425 Stations (IOI20_stations) C++17
36.3167 / 100
 1043 ms 1128 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] * 1001 + s.out[i];

	return res;
}

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

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

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 872 KB Output is correct
2 Correct 639 ms 876 KB Output is correct
3 Correct 586 ms 752 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 617 ms 876 KB Output is correct
8 Correct 869 ms 760 KB Output is correct
9 Correct 702 ms 876 KB Output is correct
10 Correct 750 ms 876 KB Output is correct
11 Correct 5 ms 868 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 4 ms 1004 KB Output is correct
15 Correct 3 ms 876 KB Output is correct
16 Correct 622 ms 872 KB Output is correct
17 Correct 510 ms 872 KB Output is correct
18 Correct 648 ms 884 KB Output is correct
19 Correct 581 ms 768 KB Output is correct
20 Correct 637 ms 876 KB Output is correct

Subtask #5
26.3167 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 531 ms 1024 KB Partially correct
2 Partially correct 442 ms 768 KB Partially correct
3 Partially correct 1043 ms 760 KB Partially correct
4 Partially correct 744 ms 768 KB Partially correct
5 Partially correct 700 ms 872 KB Partially correct
6 Partially correct 495 ms 1024 KB Partially correct
7 Partially correct 530 ms 768 KB Partially correct
8 Partially correct 3 ms 884 KB Partially correct
9 Partially correct 6 ms 768 KB Partially correct
10 Partially correct 1 ms 768 KB Partially correct
11 Partially correct 551 ms 812 KB Partially correct
12 Partially correct 640 ms 828 KB Partially correct
13 Partially correct 931 ms 876 KB Partially correct
14 Partially correct 777 ms 876 KB Partially correct
15 Partially correct 636 ms 876 KB Partially correct
16 Partially correct 602 ms 832 KB Partially correct
17 Partially correct 736 ms 872 KB Partially correct
18 Partially correct 576 ms 860 KB Partially correct
19 Partially correct 564 ms 1024 KB Partially correct
20 Partially correct 564 ms 768 KB Partially correct
21 Partially correct 69 ms 860 KB Partially correct
22 Partially correct 81 ms 848 KB Partially correct
23 Partially correct 138 ms 828 KB Partially correct
24 Partially correct 6 ms 768 KB Partially correct
25 Partially correct 5 ms 884 KB Partially correct
26 Partially correct 5 ms 872 KB Partially correct
27 Partially correct 4 ms 768 KB Partially correct
28 Partially correct 2 ms 768 KB Partially correct
29 Partially correct 639 ms 768 KB Partially correct
30 Partially correct 576 ms 784 KB Partially correct
31 Partially correct 592 ms 876 KB Partially correct
32 Partially correct 619 ms 876 KB Partially correct
33 Partially correct 540 ms 996 KB Partially correct
34 Partially correct 394 ms 772 KB Partially correct
35 Partially correct 459 ms 1128 KB Partially correct
36 Partially correct 522 ms 1008 KB Partially correct
37 Partially correct 482 ms 888 KB Partially correct
38 Partially correct 475 ms 920 KB Partially correct
39 Partially correct 522 ms 916 KB Partially correct
40 Partially correct 463 ms 768 KB Partially correct
41 Partially correct 479 ms 928 KB Partially correct
42 Partially correct 81 ms 768 KB Partially correct
43 Partially correct 113 ms 816 KB Partially correct
44 Partially correct 140 ms 832 KB Partially correct
45 Partially correct 164 ms 768 KB Partially correct
46 Partially correct 312 ms 756 KB Partially correct
47 Partially correct 331 ms 792 KB Partially correct
48 Partially correct 70 ms 824 KB Partially correct
49 Partially correct 69 ms 812 KB Partially correct