oj.uz

Submission #804866

# Submission time Handle Problem Language Result Execution time Memory
804866 2023-08-03T11:42:17 Z alvingogo Stations (IOI20_stations) C++14
100 / 100
 812 ms 764 KB 
#include "stations.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct TR{
	struct no{
		vector<int> ch;
		int lb=-1;
	};
	vector<no> v;
	void init(int x){
		v.resize(x);
	}
	void add(int x,int y){
		v[x].ch.push_back(y);
		v[y].ch.push_back(x);
	}
	int cnt=0;
	void dfs(int r,int f,int d){
		if(d%2==0){
			v[r].lb=cnt;
			cnt++;
		}
		for(auto h:v[r].ch){
			if(h!=f){
				dfs(h,r,d+1);
			}
		}
		if(d%2){
			v[r].lb=cnt;
			cnt++;
		}
	}
};
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	TR tr;
	tr.init(n);
	for(int i=0;i<n-1;i++){
		tr.add(u[i],v[i]);
	}
	tr.dfs(0,0,0);
	vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = tr.v[i].lb;
	}
	return labels;
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 548 KB Output is correct
2 Correct 373 ms 548 KB Output is correct
3 Correct 582 ms 500 KB Output is correct
4 Correct 534 ms 548 KB Output is correct
5 Correct 470 ms 544 KB Output is correct
6 Correct 348 ms 568 KB Output is correct
7 Correct 415 ms 676 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 488 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 508 KB Output is correct
2 Correct 423 ms 544 KB Output is correct
3 Correct 580 ms 504 KB Output is correct
4 Correct 564 ms 508 KB Output is correct
5 Correct 431 ms 504 KB Output is correct
6 Correct 405 ms 492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 548 KB Output is correct
2 Correct 301 ms 716 KB Output is correct
3 Correct 727 ms 504 KB Output is correct
4 Correct 547 ms 504 KB Output is correct
5 Correct 554 ms 420 KB Output is correct
6 Correct 440 ms 512 KB Output is correct
7 Correct 465 ms 524 KB Output is correct
8 Correct 1 ms 564 KB Output is correct
9 Correct 4 ms 496 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 601 ms 416 KB Output is correct
12 Correct 434 ms 588 KB Output is correct
13 Correct 409 ms 628 KB Output is correct
14 Correct 342 ms 568 KB Output is correct
15 Correct 48 ms 444 KB Output is correct
16 Correct 61 ms 548 KB Output is correct
17 Correct 94 ms 508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 424 KB Output is correct
2 Correct 601 ms 420 KB Output is correct
3 Correct 464 ms 544 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 0 ms 476 KB Output is correct
7 Correct 430 ms 504 KB Output is correct
8 Correct 778 ms 508 KB Output is correct
9 Correct 511 ms 500 KB Output is correct
10 Correct 461 ms 512 KB Output is correct
11 Correct 3 ms 472 KB Output is correct
12 Correct 3 ms 492 KB Output is correct
13 Correct 4 ms 492 KB Output is correct
14 Correct 2 ms 496 KB Output is correct
15 Correct 1 ms 444 KB Output is correct
16 Correct 409 ms 420 KB Output is correct
17 Correct 401 ms 416 KB Output is correct
18 Correct 350 ms 416 KB Output is correct
19 Correct 327 ms 500 KB Output is correct
20 Correct 365 ms 416 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 504 KB Output is correct
2 Correct 447 ms 572 KB Output is correct
3 Correct 812 ms 500 KB Output is correct
4 Correct 451 ms 532 KB Output is correct
5 Correct 575 ms 508 KB Output is correct
6 Correct 323 ms 544 KB Output is correct
7 Correct 313 ms 548 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 406 ms 576 KB Output is correct
12 Correct 413 ms 548 KB Output is correct
13 Correct 767 ms 420 KB Output is correct
14 Correct 640 ms 504 KB Output is correct
15 Correct 482 ms 420 KB Output is correct
16 Correct 383 ms 512 KB Output is correct
17 Correct 529 ms 420 KB Output is correct
18 Correct 373 ms 752 KB Output is correct
19 Correct 453 ms 584 KB Output is correct
20 Correct 361 ms 500 KB Output is correct
21 Correct 51 ms 492 KB Output is correct
22 Correct 63 ms 576 KB Output is correct
23 Correct 94 ms 544 KB Output is correct
24 Correct 5 ms 492 KB Output is correct
25 Correct 3 ms 492 KB Output is correct
26 Correct 2 ms 496 KB Output is correct
27 Correct 2 ms 492 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 503 ms 416 KB Output is correct
30 Correct 465 ms 416 KB Output is correct
31 Correct 462 ms 504 KB Output is correct
32 Correct 347 ms 500 KB Output is correct
33 Correct 435 ms 420 KB Output is correct
34 Correct 264 ms 508 KB Output is correct
35 Correct 261 ms 628 KB Output is correct
36 Correct 364 ms 704 KB Output is correct
37 Correct 420 ms 604 KB Output is correct
38 Correct 407 ms 664 KB Output is correct
39 Correct 373 ms 744 KB Output is correct
40 Correct 392 ms 764 KB Output is correct
41 Correct 363 ms 588 KB Output is correct
42 Correct 59 ms 572 KB Output is correct
43 Correct 91 ms 504 KB Output is correct
44 Correct 110 ms 544 KB Output is correct
45 Correct 119 ms 544 KB Output is correct
46 Correct 301 ms 548 KB Output is correct
47 Correct 257 ms 676 KB Output is correct
48 Correct 46 ms 564 KB Output is correct
49 Correct 42 ms 672 KB Output is correct