oj.uz

Submission #803016

# Submission time Handle Problem Language Result Execution time Memory
803016 2023-08-02T18:15:44 Z TimDee Stations (IOI20_stations) C++17
100 / 100
 808 ms 908 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;

const int N=1e3;
int l[N], r[N];
vector<int> adj[N];
int nxt=0;
int col[N];
void dfs(int u, int p, int c) {
	col[u]=c;
	l[u]=nxt++;
	for(auto&v:adj[u]) {
		if (v==p) continue;
		dfs(v,u,!c);
	}
	r[u]=nxt++;
}

vector<int> label(int n, int k, vector<int>u, vector<int> v) {
	forn(i,n) adj[i].clear(); nxt=0;
	forn(i,n-1) {
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}

	dfs(0,-1,0);
	vector<int> ans(n);
	forn(i,n) {
		if (col[i]) {
			ans[i]=l[i];
		} else {
			ans[i]=r[i];
		}
	}
	set<int> s; forn(i,n) s.insert(ans[i]);
	int mex=0;
	map<int,int> c;
	for(auto&x:s) c[x]=mex++;
	forn(i,n) ans[i]=c[ans[i]];
	return ans;
}

int is_ancestor(int l, int r, int y) {
	//x is anc of y
	return l <= y && y <= r;
}

int find_next_station(int s, int t, vector<int> adj) {
	//cout<<"? "<<s<<' '<<t<<": "; for(auto&x:adj) cout<<x<<' '; cout<<'\n';
	if (adj.size()==1) return adj[0];
	if (s > adj.back()) {
		int l=2*adj[1]-1;
		int r=2*s;
		if (is_ancestor(l,r,2*t)) {
			for (int i=1; i<adj.size()-1; ++i) {
				int l=2*adj[i], r=2*adj[i+1]-1;
				if (is_ancestor(l,r,2*t)) return adj[i];
			}
			return adj.back();
		} else {
			return adj[0];
		}
	} else {
		int l=2*s;
		int r=2*adj[adj.size()-2]+1;
		if (is_ancestor(l,r,2*t)) {
			for (int i=1; i<adj.size()-1; ++i) {
				int l=2*adj[i-1]+1, r=2*adj[i];
				if (is_ancestor(l,r,2*t)) return adj[i];
			}
			return adj[0];
		} else {
			return adj.back();
		}
	}
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:4:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
      |                   ^~~
stations.cpp:25:2: note: in expansion of macro 'forn'
   25 |  forn(i,n) adj[i].clear(); nxt=0;
      |  ^~~~
stations.cpp:25:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   25 |  forn(i,n) adj[i].clear(); nxt=0;
      |                            ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int i=1; i<adj.size()-1; ++i) {
      |                  ~^~~~~~~~~~~~~
stations.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for (int i=1; i<adj.size()-1; ++i) {
      |                  ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 744 KB Output is correct
2 Correct 421 ms 792 KB Output is correct
3 Correct 664 ms 712 KB Output is correct
4 Correct 562 ms 652 KB Output is correct
5 Correct 462 ms 748 KB Output is correct
6 Correct 425 ms 908 KB Output is correct
7 Correct 408 ms 652 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 2 ms 584 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 672 KB Output is correct
2 Correct 498 ms 664 KB Output is correct
3 Correct 808 ms 524 KB Output is correct
4 Correct 562 ms 716 KB Output is correct
5 Correct 566 ms 540 KB Output is correct
6 Correct 412 ms 800 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 664 KB Output is correct
2 Correct 442 ms 748 KB Output is correct
3 Correct 754 ms 512 KB Output is correct
4 Correct 567 ms 532 KB Output is correct
5 Correct 568 ms 672 KB Output is correct
6 Correct 339 ms 660 KB Output is correct
7 Correct 348 ms 748 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 1 ms 676 KB Output is correct
11 Correct 473 ms 520 KB Output is correct
12 Correct 362 ms 796 KB Output is correct
13 Correct 412 ms 832 KB Output is correct
14 Correct 430 ms 664 KB Output is correct
15 Correct 39 ms 548 KB Output is correct
16 Correct 61 ms 672 KB Output is correct
17 Correct 101 ms 796 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 656 KB Output is correct
2 Correct 606 ms 668 KB Output is correct
3 Correct 505 ms 672 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 0 ms 620 KB Output is correct
7 Correct 500 ms 524 KB Output is correct
8 Correct 596 ms 548 KB Output is correct
9 Correct 655 ms 676 KB Output is correct
10 Correct 492 ms 540 KB Output is correct
11 Correct 3 ms 628 KB Output is correct
12 Correct 5 ms 628 KB Output is correct
13 Correct 3 ms 628 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 1 ms 632 KB Output is correct
16 Correct 393 ms 652 KB Output is correct
17 Correct 391 ms 416 KB Output is correct
18 Correct 319 ms 544 KB Output is correct
19 Correct 437 ms 544 KB Output is correct
20 Correct 362 ms 664 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 672 KB Output is correct
2 Correct 322 ms 804 KB Output is correct
3 Correct 789 ms 660 KB Output is correct
4 Correct 410 ms 660 KB Output is correct
5 Correct 490 ms 660 KB Output is correct
6 Correct 427 ms 664 KB Output is correct
7 Correct 328 ms 656 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 0 ms 624 KB Output is correct
11 Correct 318 ms 664 KB Output is correct
12 Correct 393 ms 672 KB Output is correct
13 Correct 689 ms 528 KB Output is correct
14 Correct 602 ms 532 KB Output is correct
15 Correct 453 ms 536 KB Output is correct
16 Correct 416 ms 672 KB Output is correct
17 Correct 377 ms 548 KB Output is correct
18 Correct 401 ms 784 KB Output is correct
19 Correct 465 ms 780 KB Output is correct
20 Correct 430 ms 672 KB Output is correct
21 Correct 38 ms 620 KB Output is correct
22 Correct 46 ms 596 KB Output is correct
23 Correct 86 ms 828 KB Output is correct
24 Correct 4 ms 628 KB Output is correct
25 Correct 5 ms 748 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 2 ms 620 KB Output is correct
28 Correct 2 ms 628 KB Output is correct
29 Correct 420 ms 556 KB Output is correct
30 Correct 461 ms 416 KB Output is correct
31 Correct 399 ms 544 KB Output is correct
32 Correct 444 ms 544 KB Output is correct
33 Correct 494 ms 544 KB Output is correct
34 Correct 263 ms 672 KB Output is correct
35 Correct 396 ms 660 KB Output is correct
36 Correct 329 ms 780 KB Output is correct
37 Correct 459 ms 816 KB Output is correct
38 Correct 412 ms 788 KB Output is correct
39 Correct 370 ms 788 KB Output is correct
40 Correct 315 ms 860 KB Output is correct
41 Correct 382 ms 796 KB Output is correct
42 Correct 38 ms 672 KB Output is correct
43 Correct 75 ms 812 KB Output is correct
44 Correct 119 ms 812 KB Output is correct
45 Correct 99 ms 724 KB Output is correct
46 Correct 241 ms 548 KB Output is correct
47 Correct 278 ms 676 KB Output is correct
48 Correct 56 ms 856 KB Output is correct
49 Correct 52 ms 880 KB Output is correct