oj.uz

답안 #404346

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404346 2021-05-14T08:39:34 Z AmineTrabelsi 기지국 (IOI20_stations) C++14
100 / 100
 1122 ms 860 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
const int Mx = 1010;
int timer = 0;
int tin[Mx],tout[Mx],lab[Mx];
void dfs(int node,int par,vector<vector<int>> &tr,bool parity){
    tin[node] = timer++;
    for(auto i:tr[node]){
        if(i != par){
            dfs(i,node,tr,!parity);
        }
    }
    tout[node] = timer++;
    lab[node] = (parity ? tin[node] : tout[node]);
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    timer = 0;
    vector<int> labels(n);
    vector<vector<int>> tr(n+1,vector<int>(0));
	for (int i = 0; i < n-1; i++) {
		tr[u[i]].push_back(v[i]);
        tr[v[i]].push_back(u[i]);
	}
    dfs(0,-1,tr,1);
    for(int i=0;i<n;i++)labels[i] = lab[i]/2;
	return labels;
}
int find_next_station(int s, int t, vector<int> c) {
    if ((int)c.size() == 1) return c.back();
    if (c.front() > s){
        // s in tin
        int l = s, r = c[(int)c.size() - 2];
        if (l > t || r < t) return c.back();
        int pos = lower_bound(c.begin(), c.end(), t) - c.begin();
        return c[pos];
    }
    // s is tout
    int l = c[1], r = s;
    if (l > t || r < t) return c.front();
    int pos = upper_bound(c.begin(), c.end(), t) - c.begin() - 1;
    return c[pos];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 650 ms 672 KB Output is correct
2 Correct 533 ms 528 KB Output is correct
3 Correct 1085 ms 416 KB Output is correct
4 Correct 866 ms 488 KB Output is correct
5 Correct 613 ms 528 KB Output is correct
6 Correct 533 ms 528 KB Output is correct
7 Correct 604 ms 532 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 476 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 541 ms 480 KB Output is correct
2 Correct 639 ms 560 KB Output is correct
3 Correct 1073 ms 528 KB Output is correct
4 Correct 806 ms 400 KB Output is correct
5 Correct 632 ms 484 KB Output is correct
6 Correct 551 ms 528 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 608 ms 528 KB Output is correct
2 Correct 570 ms 652 KB Output is correct
3 Correct 1059 ms 528 KB Output is correct
4 Correct 813 ms 476 KB Output is correct
5 Correct 762 ms 528 KB Output is correct
6 Correct 503 ms 528 KB Output is correct
7 Correct 543 ms 528 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 830 ms 400 KB Output is correct
12 Correct 509 ms 860 KB Output is correct
13 Correct 474 ms 728 KB Output is correct
14 Correct 554 ms 528 KB Output is correct
15 Correct 61 ms 468 KB Output is correct
16 Correct 63 ms 528 KB Output is correct
17 Correct 120 ms 700 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1122 ms 400 KB Output is correct
2 Correct 798 ms 400 KB Output is correct
3 Correct 833 ms 532 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 558 ms 484 KB Output is correct
8 Correct 856 ms 400 KB Output is correct
9 Correct 621 ms 400 KB Output is correct
10 Correct 805 ms 400 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 4 ms 476 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 527 ms 400 KB Output is correct
17 Correct 730 ms 424 KB Output is correct
18 Correct 644 ms 428 KB Output is correct
19 Correct 590 ms 400 KB Output is correct
20 Correct 544 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 629 ms 656 KB Output is correct
2 Correct 481 ms 744 KB Output is correct
3 Correct 1002 ms 520 KB Output is correct
4 Correct 867 ms 496 KB Output is correct
5 Correct 689 ms 400 KB Output is correct
6 Correct 630 ms 652 KB Output is correct
7 Correct 432 ms 592 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 607 ms 484 KB Output is correct
12 Correct 630 ms 528 KB Output is correct
13 Correct 954 ms 476 KB Output is correct
14 Correct 848 ms 484 KB Output is correct
15 Correct 681 ms 480 KB Output is correct
16 Correct 552 ms 528 KB Output is correct
17 Correct 710 ms 400 KB Output is correct
18 Correct 474 ms 700 KB Output is correct
19 Correct 522 ms 736 KB Output is correct
20 Correct 540 ms 528 KB Output is correct
21 Correct 66 ms 468 KB Output is correct
22 Correct 71 ms 492 KB Output is correct
23 Correct 143 ms 680 KB Output is correct
24 Correct 7 ms 468 KB Output is correct
25 Correct 5 ms 476 KB Output is correct
26 Correct 4 ms 468 KB Output is correct
27 Correct 5 ms 468 KB Output is correct
28 Correct 2 ms 476 KB Output is correct
29 Correct 560 ms 488 KB Output is correct
30 Correct 553 ms 400 KB Output is correct
31 Correct 588 ms 400 KB Output is correct
32 Correct 652 ms 400 KB Output is correct
33 Correct 619 ms 488 KB Output is correct
34 Correct 440 ms 616 KB Output is correct
35 Correct 516 ms 612 KB Output is correct
36 Correct 583 ms 604 KB Output is correct
37 Correct 540 ms 556 KB Output is correct
38 Correct 547 ms 564 KB Output is correct
39 Correct 519 ms 564 KB Output is correct
40 Correct 581 ms 560 KB Output is correct
41 Correct 660 ms 576 KB Output is correct
42 Correct 84 ms 528 KB Output is correct
43 Correct 149 ms 528 KB Output is correct
44 Correct 163 ms 528 KB Output is correct
45 Correct 146 ms 528 KB Output is correct
46 Correct 319 ms 492 KB Output is correct
47 Correct 399 ms 488 KB Output is correct
48 Correct 89 ms 588 KB Output is correct
49 Correct 83 ms 648 KB Output is correct