oj.uz

Submission #308279

# Submission time Handle Problem Language Result Execution time Memory
308279 2020-09-30T18:01:47 Z Peti Stations (IOI20_stations) C++14
100 / 100
 1134 ms 1280 KB 
#include "stations.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> g;
vector<bool> volt;

int ido = 0;
void Bejar(vector<int> &labels, int akt, int t)
{
    volt[akt] = true;

    if(t%2 == 0)
        labels[akt] = ido / 2;
    ido++;

    for(int x : g[akt])
        if(!volt[x])
            Bejar(labels, x, t+1);

    if(t%2 == 1)
        labels[akt] = ido / 2;
    ido++;
    return;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    ido = 0;
    volt.assign(n, false);
    g.assign(n, vector<int>());
    for(int i = 0; i < n-1; i++)
    {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }

	std::vector<int> labels(n);

    Bejar(labels, 0, 0);

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {

    sort(c.begin(), c.end());

    if(s < c[0])
    {
        if(t < s || t > (*c.rbegin()))
            return (*c.rbegin());
        for(int x : c)
            if(x >= t)
                return x;
    }
    else
    {
        if(t > s || t <= c[0])
            return c[0];
        reverse(c.begin(), c.end());
        for(int x : c)
            if(x <= t)
                return x;
    }

	return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 1012 KB Output is correct
2 Correct 444 ms 1280 KB Output is correct
3 Correct 873 ms 640 KB Output is correct
4 Correct 665 ms 640 KB Output is correct
5 Correct 581 ms 640 KB Output is correct
6 Correct 456 ms 760 KB Output is correct
7 Correct 454 ms 792 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 644 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 768 KB Output is correct
2 Correct 601 ms 824 KB Output is correct
3 Correct 953 ms 648 KB Output is correct
4 Correct 718 ms 640 KB Output is correct
5 Correct 697 ms 644 KB Output is correct
6 Correct 583 ms 828 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 1120 KB Output is correct
2 Correct 511 ms 1008 KB Output is correct
3 Correct 1134 ms 644 KB Output is correct
4 Correct 759 ms 644 KB Output is correct
5 Correct 624 ms 648 KB Output is correct
6 Correct 480 ms 768 KB Output is correct
7 Correct 502 ms 768 KB Output is correct
8 Correct 2 ms 772 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 623 ms 640 KB Output is correct
12 Correct 556 ms 1024 KB Output is correct
13 Correct 663 ms 1020 KB Output is correct
14 Correct 523 ms 784 KB Output is correct
15 Correct 71 ms 892 KB Output is correct
16 Correct 77 ms 768 KB Output is correct
17 Correct 106 ms 820 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 640 KB Output is correct
2 Correct 785 ms 576 KB Output is correct
3 Correct 711 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 615 ms 652 KB Output is correct
8 Correct 955 ms 644 KB Output is correct
9 Correct 766 ms 648 KB Output is correct
10 Correct 697 ms 640 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 2 ms 656 KB Output is correct
16 Correct 636 ms 640 KB Output is correct
17 Correct 568 ms 648 KB Output is correct
18 Correct 587 ms 784 KB Output is correct
19 Correct 596 ms 656 KB Output is correct
20 Correct 578 ms 768 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 1024 KB Output is correct
2 Correct 550 ms 1024 KB Output is correct
3 Correct 865 ms 640 KB Output is correct
4 Correct 690 ms 640 KB Output is correct
5 Correct 678 ms 640 KB Output is correct
6 Correct 497 ms 1024 KB Output is correct
7 Correct 548 ms 796 KB Output is correct
8 Correct 3 ms 656 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 1 ms 648 KB Output is correct
11 Correct 519 ms 784 KB Output is correct
12 Correct 650 ms 824 KB Output is correct
13 Correct 935 ms 768 KB Output is correct
14 Correct 723 ms 644 KB Output is correct
15 Correct 648 ms 644 KB Output is correct
16 Correct 501 ms 768 KB Output is correct
17 Correct 588 ms 640 KB Output is correct
18 Correct 520 ms 768 KB Output is correct
19 Correct 512 ms 1008 KB Output is correct
20 Correct 577 ms 768 KB Output is correct
21 Correct 59 ms 768 KB Output is correct
22 Correct 76 ms 976 KB Output is correct
23 Correct 109 ms 824 KB Output is correct
24 Correct 6 ms 648 KB Output is correct
25 Correct 4 ms 652 KB Output is correct
26 Correct 4 ms 648 KB Output is correct
27 Correct 5 ms 800 KB Output is correct
28 Correct 2 ms 652 KB Output is correct
29 Correct 572 ms 800 KB Output is correct
30 Correct 505 ms 648 KB Output is correct
31 Correct 540 ms 644 KB Output is correct
32 Correct 586 ms 640 KB Output is correct
33 Correct 588 ms 640 KB Output is correct
34 Correct 417 ms 1016 KB Output is correct
35 Correct 566 ms 1008 KB Output is correct
36 Correct 529 ms 1108 KB Output is correct
37 Correct 470 ms 892 KB Output is correct
38 Correct 525 ms 888 KB Output is correct
39 Correct 613 ms 1136 KB Output is correct
40 Correct 464 ms 1024 KB Output is correct
41 Correct 505 ms 792 KB Output is correct
42 Correct 60 ms 844 KB Output is correct
43 Correct 112 ms 808 KB Output is correct
44 Correct 142 ms 768 KB Output is correct
45 Correct 212 ms 768 KB Output is correct
46 Correct 302 ms 824 KB Output is correct
47 Correct 343 ms 796 KB Output is correct
48 Correct 63 ms 780 KB Output is correct
49 Correct 60 ms 1024 KB Output is correct