oj.uz

Submission #415532

# Submission time Handle Problem Language Result Execution time Memory
415532 2021-06-01T08:10:34 Z Pro_ktmr Stations (IOI20_stations) C++17
100 / 100
 1264 ms 680 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
#define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)

#include "stations.h"
#include <vector>

void dfs(int v, int p, vector<int> e[], vector<int>& labels, int& c){
	labels[v] = c;
	for(auto i: e[v]){
		if(i == p) continue;
		c++;
		dfs(i, v, e, labels, c);
		c++;
	}
	if(c%2) labels[v] = c;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	vector<int> e[1000];
	rep(i, n-1){
		e[u[i]].pb(v[i]);
		e[v[i]].pb(u[i]);
	}

	vector<int> labels(n);
	int c = 0;
	dfs(0, -1, e, labels, c);

	vector<int> z = labels;
	sort(all(z));
	rep(i, n) labels[i] = lower_bound(all(z), labels[i]) - z.begin();

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	rep(i, c.size()){
		if(t == c[i]) return c[i];
	}
	if(c.back() < s){
		repi(i, 1, c.size()-1){
			if(c[i] < t && t < c[i+1]) return c[i];
		}
		if(c.back() < t && t < s) return c.back();
		return c[0];
	}
	else{
		repi(i, 1, c.size()-1){
			if(c[i-1] < t && t < c[i]) return c[i];
		}
		if(s < t && t < c.front()) return c.front();
		return c.back();
	}
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
stations.cpp:24:2: note: in expansion of macro 'rep'
   24 |  rep(i, n-1){
      |  ^~~
stations.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
stations.cpp:35:2: note: in expansion of macro 'rep'
   35 |  rep(i, n) labels[i] = lower_bound(all(z), labels[i]) - z.begin();
      |  ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
stations.cpp:41:2: note: in expansion of macro 'rep'
   41 |  rep(i, c.size()){
      |  ^~~
stations.cpp:5:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
stations.cpp:41:2: note: in expansion of macro 'rep'
   41 |  rep(i, c.size()){
      |  ^~~
stations.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
      |                               ^
stations.cpp:45:3: note: in expansion of macro 'repi'
   45 |   repi(i, 1, c.size()-1){
      |   ^~~~
stations.cpp:6:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
      |                                        ~~~^~~~
stations.cpp:45:3: note: in expansion of macro 'repi'
   45 |   repi(i, 1, c.size()-1){
      |   ^~~~
stations.cpp:6:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
      |                               ^
stations.cpp:52:3: note: in expansion of macro 'repi'
   52 |   repi(i, 1, c.size()-1){
      |   ^~~~
stations.cpp:6:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
      |                                        ~~~^~~~
stations.cpp:52:3: note: in expansion of macro 'repi'
   52 |   repi(i, 1, c.size()-1){
      |   ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 596 KB Output is correct
2 Correct 776 ms 604 KB Output is correct
3 Correct 1264 ms 468 KB Output is correct
4 Correct 825 ms 400 KB Output is correct
5 Correct 849 ms 476 KB Output is correct
6 Correct 429 ms 520 KB Output is correct
7 Correct 556 ms 616 KB Output is correct
8 Correct 6 ms 464 KB Output is correct
9 Correct 7 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 552 KB Output is correct
2 Correct 678 ms 476 KB Output is correct
3 Correct 1260 ms 544 KB Output is correct
4 Correct 737 ms 528 KB Output is correct
5 Correct 773 ms 488 KB Output is correct
6 Correct 523 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 604 KB Output is correct
2 Correct 576 ms 612 KB Output is correct
3 Correct 1115 ms 472 KB Output is correct
4 Correct 859 ms 480 KB Output is correct
5 Correct 619 ms 488 KB Output is correct
6 Correct 609 ms 636 KB Output is correct
7 Correct 568 ms 528 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 750 ms 400 KB Output is correct
12 Correct 604 ms 652 KB Output is correct
13 Correct 539 ms 680 KB Output is correct
14 Correct 536 ms 476 KB Output is correct
15 Correct 84 ms 448 KB Output is correct
16 Correct 67 ms 624 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 1069 ms 468 KB Output is correct
2 Correct 778 ms 484 KB Output is correct
3 Correct 657 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 599 ms 400 KB Output is correct
8 Correct 926 ms 400 KB Output is correct
9 Correct 866 ms 480 KB Output is correct
10 Correct 871 ms 404 KB Output is correct
11 Correct 8 ms 452 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 7 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 649 ms 452 KB Output is correct
17 Correct 574 ms 400 KB Output is correct
18 Correct 662 ms 404 KB Output is correct
19 Correct 565 ms 484 KB Output is correct
20 Correct 660 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 612 KB Output is correct
2 Correct 459 ms 612 KB Output is correct
3 Correct 1194 ms 480 KB Output is correct
4 Correct 760 ms 424 KB Output is correct
5 Correct 703 ms 400 KB Output is correct
6 Correct 482 ms 528 KB Output is correct
7 Correct 634 ms 492 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 472 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 582 ms 656 KB Output is correct
12 Correct 792 ms 520 KB Output is correct
13 Correct 1059 ms 524 KB Output is correct
14 Correct 782 ms 400 KB Output is correct
15 Correct 763 ms 488 KB Output is correct
16 Correct 600 ms 528 KB Output is correct
17 Correct 756 ms 492 KB Output is correct
18 Correct 578 ms 608 KB Output is correct
19 Correct 526 ms 600 KB Output is correct
20 Correct 568 ms 468 KB Output is correct
21 Correct 65 ms 400 KB Output is correct
22 Correct 91 ms 532 KB Output is correct
23 Correct 115 ms 540 KB Output is correct
24 Correct 7 ms 468 KB Output is correct
25 Correct 7 ms 476 KB Output is correct
26 Correct 7 ms 480 KB Output is correct
27 Correct 5 ms 464 KB Output is correct
28 Correct 3 ms 464 KB Output is correct
29 Correct 704 ms 484 KB Output is correct
30 Correct 520 ms 508 KB Output is correct
31 Correct 659 ms 488 KB Output is correct
32 Correct 795 ms 476 KB Output is correct
33 Correct 528 ms 400 KB Output is correct
34 Correct 506 ms 600 KB Output is correct
35 Correct 484 ms 604 KB Output is correct
36 Correct 766 ms 652 KB Output is correct
37 Correct 492 ms 636 KB Output is correct
38 Correct 610 ms 556 KB Output is correct
39 Correct 564 ms 616 KB Output is correct
40 Correct 571 ms 568 KB Output is correct
41 Correct 516 ms 600 KB Output is correct
42 Correct 79 ms 528 KB Output is correct
43 Correct 107 ms 528 KB Output is correct
44 Correct 161 ms 528 KB Output is correct
45 Correct 153 ms 528 KB Output is correct
46 Correct 384 ms 484 KB Output is correct
47 Correct 421 ms 528 KB Output is correct
48 Correct 64 ms 552 KB Output is correct
49 Correct 82 ms 644 KB Output is correct