oj.uz

답안 #424464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424464 2021-06-12T01:20:36 Z benedict0724 기지국 (IOI20_stations) C++17
100 / 100
 1123 ms 784 KB 
#include "stations.h"
#include <vector>
#include <algorithm>
 
using namespace std;
vector<int> adj[1000];
vector<int> labels;
int sub[1000];
 
void dfs1(int x, int p)
{
    sub[x] = 1;
    for(int i : adj[x])
    {
        if(i == p) continue;
        dfs1(i, x);
        sub[x] += sub[i];
    }
}
 
void dfs2(int x, int p, int d, int l, int r){
    if(d == 0) labels[x] = l;
    else labels[x] = r;
 
    int tmp = l;
    if(d == 0) tmp = l + 1;
    for(int i : adj[x])
    {
        if(i == p) continue;
        dfs2(i, x, !d, tmp, tmp + sub[i] - 1);
        tmp += sub[i];
    }
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    labels.resize(n);
    for(int i=0;i<n;i++) adj[i].clear();
	for(int i=0;i<n-1;i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
	}
	dfs1(0, -1);
	dfs2(0, -1, 0, 0, n-1);
	return labels;
}
 
int find_next_station(int s, int t, std::vector<int> c) {
    int k = c.size() - 1;
    int m = c[0], M = c[k];
 
    if(m > s)
    {
        if(t < s) return M;
        for(int i=0;i<k;i++)
        {
            if(t <= c[i]) return c[i];
        }
 
        return M;
    }
 
    if(t > s) return m;
    for(int i=k;i>0;i--)
    {
        if(t >= c[i]) return c[i];
    }
 
    return m;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 620 KB Output is correct
2 Correct 487 ms 624 KB Output is correct
3 Correct 1009 ms 496 KB Output is correct
4 Correct 730 ms 528 KB Output is correct
5 Correct 587 ms 504 KB Output is correct
6 Correct 539 ms 628 KB Output is correct
7 Correct 436 ms 504 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 476 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 546 ms 520 KB Output is correct
2 Correct 625 ms 536 KB Output is correct
3 Correct 1091 ms 496 KB Output is correct
4 Correct 699 ms 500 KB Output is correct
5 Correct 701 ms 400 KB Output is correct
6 Correct 517 ms 524 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 565 ms 684 KB Output is correct
2 Correct 537 ms 520 KB Output is correct
3 Correct 978 ms 500 KB Output is correct
4 Correct 810 ms 504 KB Output is correct
5 Correct 653 ms 416 KB Output is correct
6 Correct 592 ms 632 KB Output is correct
7 Correct 499 ms 500 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 694 ms 632 KB Output is correct
12 Correct 519 ms 740 KB Output is correct
13 Correct 535 ms 728 KB Output is correct
14 Correct 516 ms 528 KB Output is correct
15 Correct 67 ms 420 KB Output is correct
16 Correct 77 ms 548 KB Output is correct
17 Correct 130 ms 640 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1057 ms 400 KB Output is correct
2 Correct 665 ms 400 KB Output is correct
3 Correct 663 ms 400 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 4 ms 448 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 742 ms 500 KB Output is correct
8 Correct 1123 ms 480 KB Output is correct
9 Correct 777 ms 528 KB Output is correct
10 Correct 750 ms 508 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 5 ms 468 KB Output is correct
14 Correct 3 ms 464 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 682 ms 520 KB Output is correct
17 Correct 640 ms 504 KB Output is correct
18 Correct 645 ms 504 KB Output is correct
19 Correct 546 ms 428 KB Output is correct
20 Correct 577 ms 400 KB Output is correct

Subtask #5
61.0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 628 ms 528 KB Output is correct
2 Correct 555 ms 528 KB Output is correct
3 Correct 1081 ms 400 KB Output is correct
4 Correct 873 ms 504 KB Output is correct
5 Correct 642 ms 500 KB Output is correct
6 Correct 544 ms 632 KB Output is correct
7 Correct 532 ms 500 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 0 ms 464 KB Output is correct
11 Correct 546 ms 576 KB Output is correct
12 Correct 692 ms 508 KB Output is correct
13 Correct 934 ms 528 KB Output is correct
14 Correct 859 ms 504 KB Output is correct
15 Correct 638 ms 528 KB Output is correct
16 Correct 520 ms 500 KB Output is correct
17 Correct 727 ms 400 KB Output is correct
18 Correct 543 ms 624 KB Output is correct
19 Correct 571 ms 592 KB Output is correct
20 Correct 431 ms 528 KB Output is correct
21 Correct 68 ms 404 KB Output is correct
22 Correct 81 ms 604 KB Output is correct
23 Correct 110 ms 528 KB Output is correct
24 Correct 5 ms 460 KB Output is correct
25 Correct 5 ms 472 KB Output is correct
26 Correct 4 ms 448 KB Output is correct
27 Correct 4 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 677 ms 400 KB Output is correct
30 Correct 529 ms 504 KB Output is correct
31 Correct 532 ms 400 KB Output is correct
32 Correct 661 ms 520 KB Output is correct
33 Correct 550 ms 400 KB Output is correct
34 Correct 275 ms 624 KB Output is correct
35 Correct 486 ms 660 KB Output is correct
36 Correct 557 ms 644 KB Output is correct
37 Correct 615 ms 628 KB Output is correct
38 Correct 631 ms 720 KB Output is correct
39 Correct 519 ms 592 KB Output is correct
40 Correct 493 ms 712 KB Output is correct
41 Correct 513 ms 628 KB Output is correct
42 Correct 77 ms 644 KB Output is correct
43 Correct 136 ms 588 KB Output is correct
44 Correct 168 ms 528 KB Output is correct
45 Correct 214 ms 528 KB Output is correct
46 Correct 343 ms 520 KB Output is correct
47 Correct 351 ms 528 KB Output is correct
48 Correct 73 ms 536 KB Output is correct
49 Correct 54 ms 784 KB Output is correct