oj.uz

Submission #434453

# Submission time Handle Problem Language Result Execution time Memory
434453 2021-06-21T10:22:04 Z arayi Stations (IOI20_stations) C++17
100 / 100
 1051 ms 784 KB 
#include "stations.h"
#include <iostream>
#include <algorithm>
#include <vector>
#define ad push_back
using namespace std;

const int N = 1010;
int n;
vector<int> g[N], l;
vector<pair<int, int> > a;
int xr[N], ti;
void dfs(int v, int par)
{
	ti++;
	if(xr[v]%2==0) a.ad({ti,v});
	for(auto p : g[v])
	{
		if(p==par) continue;
		xr[p]=1+xr[v];
		dfs(p,v);
	}
	ti++;
	if(xr[v]%2==1) a.ad({ti, v});
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	::n=n;
	l.clear(), a.clear();
	for (int i = 0; i < n; i++) g[i].clear(),xr[i]=0;
	ti=0;
	l.resize(n);
	for (int i = 0; i < n - 1; i++) {
		g[u[i]].ad(v[i]);
		g[v[i]].ad(u[i]);
	}
	dfs(0, 0);
	sort(a.begin(), a.end());
	for (int i = 0; i < a.size(); i++) l[a[i].second] = i;
	return l;
}

int find_next_station(int s, int t, std::vector<int> c) 
{
	if(c.size() == 1) return c[0];
	sort(c.begin(), c.end());
	if(s < c[0])
	{
		int nx = s;
		for(auto p : c)
		{
			if(t > nx && t <= p) return p;
			nx = p;
		}
		return c.back();
	}
	else
	{
		int nx = c[1];
		for (int i = 2; i < c.size(); i++)
		{
			if(t >= nx && t < c[i]) return nx;
			nx = c[i];
		}
		if(t >= nx && t < s) return nx;
		return c[0];
	}
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < a.size(); i++) l[a[i].second] = i;
      |                  ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 2; i < c.size(); i++)
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 656 KB Output is correct
2 Correct 511 ms 640 KB Output is correct
3 Correct 992 ms 504 KB Output is correct
4 Correct 831 ms 400 KB Output is correct
5 Correct 639 ms 400 KB Output is correct
6 Correct 491 ms 520 KB Output is correct
7 Correct 497 ms 640 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 560 KB Output is correct
2 Correct 661 ms 520 KB Output is correct
3 Correct 984 ms 400 KB Output is correct
4 Correct 696 ms 400 KB Output is correct
5 Correct 733 ms 544 KB Output is correct
6 Correct 468 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 656 KB Output is correct
2 Correct 501 ms 640 KB Output is correct
3 Correct 995 ms 512 KB Output is correct
4 Correct 763 ms 544 KB Output is correct
5 Correct 704 ms 512 KB Output is correct
6 Correct 525 ms 636 KB Output is correct
7 Correct 532 ms 640 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 711 ms 400 KB Output is correct
12 Correct 542 ms 620 KB Output is correct
13 Correct 534 ms 740 KB Output is correct
14 Correct 552 ms 528 KB Output is correct
15 Correct 59 ms 556 KB Output is correct
16 Correct 84 ms 528 KB Output is correct
17 Correct 166 ms 528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1015 ms 400 KB Output is correct
2 Correct 676 ms 496 KB Output is correct
3 Correct 616 ms 508 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 678 ms 496 KB Output is correct
8 Correct 1025 ms 400 KB Output is correct
9 Correct 798 ms 404 KB Output is correct
10 Correct 644 ms 520 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 640 ms 400 KB Output is correct
17 Correct 589 ms 640 KB Output is correct
18 Correct 608 ms 516 KB Output is correct
19 Correct 663 ms 512 KB Output is correct
20 Correct 538 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 624 KB Output is correct
2 Correct 594 ms 656 KB Output is correct
3 Correct 1029 ms 476 KB Output is correct
4 Correct 837 ms 400 KB Output is correct
5 Correct 649 ms 404 KB Output is correct
6 Correct 575 ms 656 KB Output is correct
7 Correct 507 ms 508 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 519 ms 520 KB Output is correct
12 Correct 607 ms 528 KB Output is correct
13 Correct 1051 ms 404 KB Output is correct
14 Correct 804 ms 516 KB Output is correct
15 Correct 687 ms 636 KB Output is correct
16 Correct 598 ms 516 KB Output is correct
17 Correct 746 ms 516 KB Output is correct
18 Correct 469 ms 748 KB Output is correct
19 Correct 656 ms 632 KB Output is correct
20 Correct 549 ms 528 KB Output is correct
21 Correct 64 ms 604 KB Output is correct
22 Correct 65 ms 548 KB Output is correct
23 Correct 97 ms 528 KB Output is correct
24 Correct 4 ms 420 KB Output is correct
25 Correct 7 ms 468 KB Output is correct
26 Correct 7 ms 464 KB Output is correct
27 Correct 4 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 500 ms 400 KB Output is correct
30 Correct 590 ms 528 KB Output is correct
31 Correct 621 ms 400 KB Output is correct
32 Correct 572 ms 516 KB Output is correct
33 Correct 572 ms 400 KB Output is correct
34 Correct 400 ms 784 KB Output is correct
35 Correct 470 ms 644 KB Output is correct
36 Correct 555 ms 736 KB Output is correct
37 Correct 612 ms 628 KB Output is correct
38 Correct 473 ms 616 KB Output is correct
39 Correct 491 ms 740 KB Output is correct
40 Correct 536 ms 748 KB Output is correct
41 Correct 417 ms 636 KB Output is correct
42 Correct 67 ms 708 KB Output is correct
43 Correct 121 ms 660 KB Output is correct
44 Correct 131 ms 532 KB Output is correct
45 Correct 209 ms 608 KB Output is correct
46 Correct 411 ms 512 KB Output is correct
47 Correct 380 ms 528 KB Output is correct
48 Correct 61 ms 660 KB Output is correct
49 Correct 81 ms 676 KB Output is correct