oj.uz

Submission #311941

# Submission time Handle Problem Language Result Execution time Memory
311941 2020-10-12T03:32:36 Z Mackerel_Pike Stations (IOI20_stations) C++14
100 / 100
 1184 ms 1116 KB 
#include "stations.h"
#include<bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1005;

int clk = 0;
int in[maxn], out[maxn];
vector<int> ans;
vector<int> g[maxn];

void dfs(int u, int p, int d){
	in[u] = ++clk;
	FOR(i, 0, g[u].size()){
		int v = g[u][i];
		if(v == p)
			continue;
		dfs(v, u, d + 1);
	}
	out[u] = ++clk;
	if(d & 1)
		ans[u] = out[u];
	else
		ans[u] = in[u];
	return;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
	FOR(i, 0, n)	
		g[i].clear();
	clk = 0;
	FOR(i, 0, n - 1){
		int u_ = u[i], v_ = v[i];
		g[u_].PB(v_);
		g[v_].PB(u_);
	}
	
	ans.resize(n);
	dfs(0, -1, 0);	
	vector<int> tmp = ans;
	sort(tmp.begin(), tmp.end());
	FOR(i, 0, n)
		ans[i] = lower_bound(tmp.begin(), tmp.end(), ans[i]) - tmp.begin();
	return ans;
}

int find_next_station(int s, int t, vector<int> c){
	if(s <= c[0]){
		FOR(i, 0, c.size() - 1) if(t >= s && t <= c[i])
			return c[i];
		return c[c.size() - 1];
	}
	else{
		for(int i = c.size() - 1; i; --i) if(t >= c[i] && t <= s)
			return c[i];
		return c[0];
	}
}

Compilation message

stations.cpp: In function 'void dfs(int, int, int)':
stations.cpp:6:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                         ^
stations.cpp:28:2: note: in expansion of macro 'FOR'
   28 |  FOR(i, 0, g[u].size()){
      |  ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:6:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                         ^
stations.cpp:63:3: note: in expansion of macro 'FOR'
   63 |   FOR(i, 0, c.size() - 1) if(t >= s && t <= c[i])
      |   ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 976 KB Output is correct
2 Correct 460 ms 1116 KB Output is correct
3 Correct 971 ms 768 KB Output is correct
4 Correct 874 ms 868 KB Output is correct
5 Correct 787 ms 872 KB Output is correct
6 Correct 598 ms 1024 KB Output is correct
7 Correct 540 ms 1024 KB Output is correct
8 Correct 3 ms 868 KB Output is correct
9 Correct 4 ms 868 KB Output is correct
10 Correct 2 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 768 KB Output is correct
2 Correct 570 ms 768 KB Output is correct
3 Correct 1043 ms 768 KB Output is correct
4 Correct 778 ms 768 KB Output is correct
5 Correct 606 ms 768 KB Output is correct
6 Correct 463 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 1024 KB Output is correct
2 Correct 483 ms 1024 KB Output is correct
3 Correct 932 ms 784 KB Output is correct
4 Correct 735 ms 768 KB Output is correct
5 Correct 625 ms 768 KB Output is correct
6 Correct 472 ms 1024 KB Output is correct
7 Correct 532 ms 1024 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 721 ms 768 KB Output is correct
12 Correct 518 ms 1024 KB Output is correct
13 Correct 466 ms 1032 KB Output is correct
14 Correct 512 ms 812 KB Output is correct
15 Correct 77 ms 908 KB Output is correct
16 Correct 90 ms 832 KB Output is correct
17 Correct 125 ms 804 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 983 ms 872 KB Output is correct
2 Correct 878 ms 872 KB Output is correct
3 Correct 790 ms 872 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 789 ms 768 KB Output is correct
8 Correct 892 ms 768 KB Output is correct
9 Correct 918 ms 872 KB Output is correct
10 Correct 745 ms 868 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 6 ms 672 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 4 ms 768 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 507 ms 768 KB Output is correct
17 Correct 535 ms 768 KB Output is correct
18 Correct 520 ms 768 KB Output is correct
19 Correct 468 ms 768 KB Output is correct
20 Correct 542 ms 768 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 1024 KB Output is correct
2 Correct 628 ms 1024 KB Output is correct
3 Correct 966 ms 872 KB Output is correct
4 Correct 914 ms 872 KB Output is correct
5 Correct 627 ms 876 KB Output is correct
6 Correct 600 ms 1024 KB Output is correct
7 Correct 588 ms 776 KB Output is correct
8 Correct 3 ms 868 KB Output is correct
9 Correct 5 ms 868 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 448 ms 792 KB Output is correct
12 Correct 543 ms 812 KB Output is correct
13 Correct 1184 ms 768 KB Output is correct
14 Correct 695 ms 868 KB Output is correct
15 Correct 811 ms 868 KB Output is correct
16 Correct 614 ms 768 KB Output is correct
17 Correct 585 ms 768 KB Output is correct
18 Correct 620 ms 1024 KB Output is correct
19 Correct 486 ms 1024 KB Output is correct
20 Correct 447 ms 808 KB Output is correct
21 Correct 61 ms 860 KB Output is correct
22 Correct 73 ms 768 KB Output is correct
23 Correct 112 ms 768 KB Output is correct
24 Correct 5 ms 872 KB Output is correct
25 Correct 6 ms 768 KB Output is correct
26 Correct 6 ms 768 KB Output is correct
27 Correct 3 ms 768 KB Output is correct
28 Correct 2 ms 864 KB Output is correct
29 Correct 721 ms 872 KB Output is correct
30 Correct 495 ms 872 KB Output is correct
31 Correct 498 ms 800 KB Output is correct
32 Correct 528 ms 868 KB Output is correct
33 Correct 500 ms 872 KB Output is correct
34 Correct 339 ms 1024 KB Output is correct
35 Correct 444 ms 1024 KB Output is correct
36 Correct 475 ms 1024 KB Output is correct
37 Correct 457 ms 1008 KB Output is correct
38 Correct 480 ms 1024 KB Output is correct
39 Correct 451 ms 1008 KB Output is correct
40 Correct 498 ms 1024 KB Output is correct
41 Correct 472 ms 1012 KB Output is correct
42 Correct 83 ms 800 KB Output is correct
43 Correct 133 ms 788 KB Output is correct
44 Correct 163 ms 776 KB Output is correct
45 Correct 196 ms 768 KB Output is correct
46 Correct 387 ms 800 KB Output is correct
47 Correct 412 ms 776 KB Output is correct
48 Correct 64 ms 1024 KB Output is correct
49 Correct 81 ms 1024 KB Output is correct