oj.uz

Submission #308161

# Submission time Handle Problem Language Result Execution time Memory
308161 2020-09-30T07:21:25 Z jwvg0425 Stations (IOI20_stations) C++17
100 / 100
 991 ms 1152 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 depth[1005] = { 0, };
	int vis = 0;

	void dfs(int root)
	{
		if (depth[root] % 2 == 0)
		{
			in[root] = vis;
			vis++;
		}

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

		if (depth[root] % 2 == 1)
		{
			out[root] = vis;
			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++)
	{
		if (s.depth[i] % 2 == 0)
			res[i] = s.in[i];
		else
			res[i] = s.out[i];
	}

	return res;
}

int find_next_station(int s, int t, vector<int> c)
{
	// s = in time, cs = out time
	if (s < c[0])
	{
		int pc = s;
		for (int i = 0; i < c.size(); i++)
		{
			if (t > pc && t <= c[i])
				return c[i];

			pc = c[i];
		}

		return c.back();
	}
	else
	{
		// s = out time, cs = in time
		for (int i = 0; i < c.size(); i++)
		{
			int nc = (i == c.size() - 1) ? (s + 1) : c[i + 1];
			if (t >= c[i] && t < nc)
				return c[i];
		}

		return c[0];
	}
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = 0; i < c.size(); i++)
      |                   ~~^~~~~~~~~~
stations.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int i = 0; i < c.size(); i++)
      |                   ~~^~~~~~~~~~
stations.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    int nc = (i == c.size() - 1) ? (s + 1) : c[i + 1];
      |              ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 1024 KB Output is correct
2 Correct 472 ms 1024 KB Output is correct
3 Correct 923 ms 868 KB Output is correct
4 Correct 865 ms 768 KB Output is correct
5 Correct 682 ms 872 KB Output is correct
6 Correct 472 ms 1024 KB Output is correct
7 Correct 534 ms 900 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 864 KB Output is correct
10 Correct 1 ms 868 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 808 KB Output is correct
2 Correct 579 ms 768 KB Output is correct
3 Correct 991 ms 760 KB Output is correct
4 Correct 675 ms 768 KB Output is correct
5 Correct 685 ms 868 KB Output is correct
6 Correct 537 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 1024 KB Output is correct
2 Correct 491 ms 1016 KB Output is correct
3 Correct 966 ms 768 KB Output is correct
4 Correct 676 ms 864 KB Output is correct
5 Correct 694 ms 784 KB Output is correct
6 Correct 460 ms 1000 KB Output is correct
7 Correct 447 ms 768 KB Output is correct
8 Correct 2 ms 868 KB Output is correct
9 Correct 4 ms 868 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 604 ms 864 KB Output is correct
12 Correct 464 ms 1120 KB Output is correct
13 Correct 532 ms 1024 KB Output is correct
14 Correct 438 ms 812 KB Output is correct
15 Correct 53 ms 860 KB Output is correct
16 Correct 71 ms 904 KB Output is correct
17 Correct 100 ms 816 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 764 KB Output is correct
2 Correct 666 ms 768 KB Output is correct
3 Correct 747 ms 776 KB Output is correct
4 Correct 3 ms 864 KB Output is correct
5 Correct 6 ms 868 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 593 ms 868 KB Output is correct
8 Correct 901 ms 872 KB Output is correct
9 Correct 675 ms 768 KB Output is correct
10 Correct 625 ms 784 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 7 ms 768 KB Output is correct
13 Correct 5 ms 864 KB Output is correct
14 Correct 4 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 529 ms 868 KB Output is correct
17 Correct 503 ms 880 KB Output is correct
18 Correct 506 ms 872 KB Output is correct
19 Correct 479 ms 864 KB Output is correct
20 Correct 500 ms 760 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 1024 KB Output is correct
2 Correct 507 ms 1012 KB Output is correct
3 Correct 984 ms 872 KB Output is correct
4 Correct 779 ms 868 KB Output is correct
5 Correct 697 ms 872 KB Output is correct
6 Correct 503 ms 1024 KB Output is correct
7 Correct 472 ms 916 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 1152 KB Output is correct
11 Correct 473 ms 796 KB Output is correct
12 Correct 537 ms 820 KB Output is correct
13 Correct 884 ms 768 KB Output is correct
14 Correct 769 ms 868 KB Output is correct
15 Correct 709 ms 868 KB Output is correct
16 Correct 471 ms 768 KB Output is correct
17 Correct 617 ms 896 KB Output is correct
18 Correct 492 ms 776 KB Output is correct
19 Correct 474 ms 1084 KB Output is correct
20 Correct 523 ms 768 KB Output is correct
21 Correct 61 ms 768 KB Output is correct
22 Correct 76 ms 768 KB Output is correct
23 Correct 101 ms 820 KB Output is correct
24 Correct 5 ms 876 KB Output is correct
25 Correct 7 ms 768 KB Output is correct
26 Correct 7 ms 768 KB Output is correct
27 Correct 4 ms 768 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 728 ms 768 KB Output is correct
30 Correct 721 ms 872 KB Output is correct
31 Correct 728 ms 768 KB Output is correct
32 Correct 513 ms 864 KB Output is correct
33 Correct 587 ms 800 KB Output is correct
34 Correct 385 ms 768 KB Output is correct
35 Correct 462 ms 1024 KB Output is correct
36 Correct 517 ms 1024 KB Output is correct
37 Correct 528 ms 920 KB Output is correct
38 Correct 527 ms 1052 KB Output is correct
39 Correct 476 ms 796 KB Output is correct
40 Correct 476 ms 760 KB Output is correct
41 Correct 533 ms 888 KB Output is correct
42 Correct 71 ms 828 KB Output is correct
43 Correct 140 ms 768 KB Output is correct
44 Correct 135 ms 776 KB Output is correct
45 Correct 155 ms 812 KB Output is correct
46 Correct 326 ms 768 KB Output is correct
47 Correct 327 ms 796 KB Output is correct
48 Correct 79 ms 824 KB Output is correct
49 Correct 76 ms 812 KB Output is correct