oj.uz

Submission #413114

# Submission time Handle Problem Language Result Execution time Memory
413114 2021-05-28T09:07:44 Z BJoozz Stations (IOI20_stations) C++14
100 / 100
 1242 ms 764 KB 
#include "stations.h"

#include<bits/stdc++.h>
using namespace std;
const int MAX=1000+4,M2=5e5+3;

#define pb push_back
vector < int > pr[MAX];
int in[MAX];
int tim=0;
void dfs(int v,int vpa,bool h){
    if(!h) in[v]=tim++;
    for(int u:pr[v])if(u!=vpa)
        dfs(u,v,!h);
    if(h) in[v]=tim++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	for(int i=0;i<n;i++) pr[i].clear();
	tim=0;
	for (int i = 0; i < n-1; i++){
        pr[u[i]].pb(v[i]);
        pr[v[i]].pb(u[i]);
	}
	dfs(0,0,0);

	for (int i = 0; i < n; i++) {
		labels[i] = in[i];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(s<c[0]){
        if(t<s) return c.back();
        int b=0,e=int(c.size())-2,an=c.back();
        if(s==0) e++;
        while(b<=e){
            int m=b+e>>1;
            if(t<=c[m]){
                an=c[m];
                e=m-1;

            }
            else b=m+1;
        }
        return an;
	}
	else{
        if(t>s) return c[0];
        int b=1,e=int(c.size())-1,an=c[0];
        while(b<=e){
            int m=b+e>>1;
            if(t>=c[m]){
                an=c[m];b=m+1;

            }
            else e=m-1;
        }
        return an;
	}
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:39:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |             int m=b+e>>1;
      |                   ~^~
stations.cpp:53:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |             int m=b+e>>1;
      |                   ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 655 ms 528 KB Output is correct
2 Correct 583 ms 640 KB Output is correct
3 Correct 1083 ms 400 KB Output is correct
4 Correct 881 ms 512 KB Output is correct
5 Correct 575 ms 504 KB Output is correct
6 Correct 610 ms 520 KB Output is correct
7 Correct 494 ms 528 KB Output is correct
8 Correct 4 ms 616 KB Output is correct
9 Correct 5 ms 572 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 600 ms 512 KB Output is correct
2 Correct 561 ms 588 KB Output is correct
3 Correct 994 ms 496 KB Output is correct
4 Correct 908 ms 516 KB Output is correct
5 Correct 808 ms 400 KB Output is correct
6 Correct 609 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 508 KB Output is correct
2 Correct 432 ms 508 KB Output is correct
3 Correct 1242 ms 400 KB Output is correct
4 Correct 753 ms 400 KB Output is correct
5 Correct 668 ms 516 KB Output is correct
6 Correct 463 ms 624 KB Output is correct
7 Correct 532 ms 512 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 578 ms 520 KB Output is correct
12 Correct 653 ms 632 KB Output is correct
13 Correct 584 ms 644 KB Output is correct
14 Correct 509 ms 572 KB Output is correct
15 Correct 63 ms 580 KB Output is correct
16 Correct 86 ms 528 KB Output is correct
17 Correct 157 ms 656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1146 ms 400 KB Output is correct
2 Correct 765 ms 520 KB Output is correct
3 Correct 721 ms 400 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 668 ms 512 KB Output is correct
8 Correct 1023 ms 400 KB Output is correct
9 Correct 779 ms 540 KB Output is correct
10 Correct 717 ms 520 KB Output is correct
11 Correct 7 ms 668 KB Output is correct
12 Correct 5 ms 464 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 604 ms 520 KB Output is correct
17 Correct 652 ms 560 KB Output is correct
18 Correct 572 ms 400 KB Output is correct
19 Correct 610 ms 400 KB Output is correct
20 Correct 678 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 644 KB Output is correct
2 Correct 591 ms 504 KB Output is correct
3 Correct 1033 ms 512 KB Output is correct
4 Correct 547 ms 516 KB Output is correct
5 Correct 846 ms 400 KB Output is correct
6 Correct 620 ms 504 KB Output is correct
7 Correct 536 ms 512 KB Output is correct
8 Correct 4 ms 448 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 567 ms 496 KB Output is correct
12 Correct 746 ms 580 KB Output is correct
13 Correct 974 ms 496 KB Output is correct
14 Correct 759 ms 400 KB Output is correct
15 Correct 741 ms 516 KB Output is correct
16 Correct 614 ms 528 KB Output is correct
17 Correct 679 ms 400 KB Output is correct
18 Correct 665 ms 640 KB Output is correct
19 Correct 561 ms 608 KB Output is correct
20 Correct 450 ms 528 KB Output is correct
21 Correct 73 ms 576 KB Output is correct
22 Correct 84 ms 640 KB Output is correct
23 Correct 104 ms 720 KB Output is correct
24 Correct 7 ms 464 KB Output is correct
25 Correct 6 ms 476 KB Output is correct
26 Correct 7 ms 476 KB Output is correct
27 Correct 7 ms 468 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 596 ms 400 KB Output is correct
30 Correct 572 ms 400 KB Output is correct
31 Correct 718 ms 404 KB Output is correct
32 Correct 472 ms 400 KB Output is correct
33 Correct 623 ms 512 KB Output is correct
34 Correct 370 ms 512 KB Output is correct
35 Correct 554 ms 736 KB Output is correct
36 Correct 595 ms 640 KB Output is correct
37 Correct 617 ms 624 KB Output is correct
38 Correct 628 ms 764 KB Output is correct
39 Correct 476 ms 764 KB Output is correct
40 Correct 492 ms 640 KB Output is correct
41 Correct 640 ms 724 KB Output is correct
42 Correct 60 ms 528 KB Output is correct
43 Correct 136 ms 588 KB Output is correct
44 Correct 134 ms 528 KB Output is correct
45 Correct 242 ms 524 KB Output is correct
46 Correct 369 ms 528 KB Output is correct
47 Correct 289 ms 528 KB Output is correct
48 Correct 81 ms 656 KB Output is correct
49 Correct 65 ms 680 KB Output is correct