oj.uz

Submission #307695

# Submission time Handle Problem Language Result Execution time Memory
307695 2020-09-29T06:11:54 Z CodePlatina Stations (IOI20_stations) C++14
100 / 100
 974 ms 1268 KB 
#include "stations.h"
#include <vector>

using namespace std;

vector<int> gph[1010];
int ord[1010];
int cnt = 0;

void dfs(int x, int p, bool flag)
{
    if(flag) ord[x] = ++cnt;
    for(auto y : gph[x]) if(y != p) dfs(y, x, !flag);
    if(!flag) ord[x] = ++cnt;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	vector<int> labels(n);
	for(int i = 0; i < n; ++i) ord[i] = 0, vector<int>().swap(gph[i]);
	cnt = 0;
	for(int i = 0; i < n - 1; ++i)
    {
        gph[u[i]].push_back(v[i]);
        gph[v[i]].push_back(u[i]);
    }
    dfs(0, 0, false);
    for(int i = 0; i < n; ++i) labels[i] = ord[i];
    return labels;
}

int find_next_station(int s, int t, vector<int> c)
{
    int n = c.size();
    if(s < c[0])
    {
        int pr = s;
        for(int i = 0; i < n - 1; ++i)
        {
            if(pr < t && t <= c[i]) return c[i];
            pr = c[i];
        }
        return c[n - 1];
    }
    else
    {
        int pr = s;
        for(int i = n - 1; i >= 1; --i)
        {
            if(c[i] <= t && t < pr) return c[i];
            pr = c[i];
        }
        return c[0];
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 1024 KB Output is correct
2 Correct 458 ms 1024 KB Output is correct
3 Correct 878 ms 888 KB Output is correct
4 Correct 759 ms 768 KB Output is correct
5 Correct 643 ms 776 KB Output is correct
6 Correct 556 ms 1024 KB Output is correct
7 Correct 589 ms 768 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 820 KB Output is correct
2 Correct 557 ms 836 KB Output is correct
3 Correct 974 ms 880 KB Output is correct
4 Correct 762 ms 884 KB Output is correct
5 Correct 659 ms 880 KB Output is correct
6 Correct 486 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 1024 KB Output is correct
2 Correct 553 ms 1016 KB Output is correct
3 Correct 963 ms 768 KB Output is correct
4 Correct 691 ms 768 KB Output is correct
5 Correct 653 ms 768 KB Output is correct
6 Correct 452 ms 1024 KB Output is correct
7 Correct 463 ms 788 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 3 ms 884 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 661 ms 768 KB Output is correct
12 Correct 500 ms 1024 KB Output is correct
13 Correct 492 ms 1024 KB Output is correct
14 Correct 483 ms 848 KB Output is correct
15 Correct 57 ms 880 KB Output is correct
16 Correct 66 ms 852 KB Output is correct
17 Correct 116 ms 824 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 896 KB Output is correct
2 Correct 749 ms 892 KB Output is correct
3 Correct 722 ms 880 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 5 ms 880 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 718 ms 888 KB Output is correct
8 Correct 905 ms 896 KB Output is correct
9 Correct 667 ms 892 KB Output is correct
10 Correct 602 ms 896 KB Output is correct
11 Correct 7 ms 896 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 5 ms 896 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 1 ms 884 KB Output is correct
16 Correct 499 ms 1040 KB Output is correct
17 Correct 505 ms 892 KB Output is correct
18 Correct 493 ms 888 KB Output is correct
19 Correct 477 ms 768 KB Output is correct
20 Correct 487 ms 1040 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 1024 KB Output is correct
2 Correct 452 ms 1024 KB Output is correct
3 Correct 946 ms 888 KB Output is correct
4 Correct 656 ms 768 KB Output is correct
5 Correct 594 ms 880 KB Output is correct
6 Correct 447 ms 1024 KB Output is correct
7 Correct 447 ms 788 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 1012 KB Output is correct
10 Correct 0 ms 888 KB Output is correct
11 Correct 455 ms 768 KB Output is correct
12 Correct 530 ms 768 KB Output is correct
13 Correct 835 ms 880 KB Output is correct
14 Correct 697 ms 888 KB Output is correct
15 Correct 577 ms 884 KB Output is correct
16 Correct 457 ms 1024 KB Output is correct
17 Correct 580 ms 892 KB Output is correct
18 Correct 446 ms 896 KB Output is correct
19 Correct 457 ms 1008 KB Output is correct
20 Correct 464 ms 832 KB Output is correct
21 Correct 55 ms 876 KB Output is correct
22 Correct 68 ms 856 KB Output is correct
23 Correct 112 ms 832 KB Output is correct
24 Correct 5 ms 768 KB Output is correct
25 Correct 4 ms 768 KB Output is correct
26 Correct 6 ms 1020 KB Output is correct
27 Correct 4 ms 884 KB Output is correct
28 Correct 1 ms 892 KB Output is correct
29 Correct 518 ms 768 KB Output is correct
30 Correct 518 ms 888 KB Output is correct
31 Correct 514 ms 768 KB Output is correct
32 Correct 530 ms 768 KB Output is correct
33 Correct 507 ms 880 KB Output is correct
34 Correct 338 ms 776 KB Output is correct
35 Correct 428 ms 1024 KB Output is correct
36 Correct 474 ms 1268 KB Output is correct
37 Correct 438 ms 768 KB Output is correct
38 Correct 457 ms 812 KB Output is correct
39 Correct 469 ms 796 KB Output is correct
40 Correct 484 ms 796 KB Output is correct
41 Correct 553 ms 808 KB Output is correct
42 Correct 57 ms 844 KB Output is correct
43 Correct 112 ms 768 KB Output is correct
44 Correct 122 ms 832 KB Output is correct
45 Correct 227 ms 768 KB Output is correct
46 Correct 328 ms 836 KB Output is correct
47 Correct 375 ms 796 KB Output is correct
48 Correct 81 ms 828 KB Output is correct
49 Correct 66 ms 820 KB Output is correct