oj.uz

Submission #308276

# Submission time Handle Problem Language Result Execution time Memory
308276 2020-09-30T17:49:04 Z Peti Stations (IOI20_stations) C++14
76 / 100
 1041 ms 1108 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;
    ido++;

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

    if(t%2 == 1)
        labels[akt] = ido;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 524 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 484 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 1016 KB Output is correct
2 Correct 489 ms 1016 KB Output is correct
3 Correct 947 ms 644 KB Output is correct
4 Correct 688 ms 640 KB Output is correct
5 Correct 593 ms 648 KB Output is correct
6 Correct 459 ms 1000 KB Output is correct
7 Correct 454 ms 784 KB Output is correct
8 Correct 3 ms 772 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 614 ms 772 KB Output is correct
12 Correct 498 ms 1108 KB Output is correct
13 Correct 678 ms 976 KB Output is correct
14 Correct 447 ms 828 KB Output is correct
15 Correct 73 ms 888 KB Output is correct
16 Correct 69 ms 852 KB Output is correct
17 Correct 109 ms 772 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 648 KB Output is correct
2 Correct 801 ms 776 KB Output is correct
3 Correct 745 ms 644 KB Output is correct
4 Correct 2 ms 656 KB Output is correct
5 Correct 4 ms 644 KB Output is correct
6 Correct 0 ms 648 KB Output is correct
7 Correct 594 ms 640 KB Output is correct
8 Correct 988 ms 644 KB Output is correct
9 Correct 669 ms 644 KB Output is correct
10 Correct 608 ms 640 KB Output is correct
11 Correct 9 ms 640 KB Output is correct
12 Correct 7 ms 644 KB Output is correct
13 Correct 5 ms 784 KB Output is correct
14 Correct 4 ms 656 KB Output is correct
15 Correct 3 ms 656 KB Output is correct
16 Correct 621 ms 640 KB Output is correct
17 Correct 626 ms 640 KB Output is correct
18 Correct 568 ms 784 KB Output is correct
19 Correct 572 ms 652 KB Output is correct
20 Correct 528 ms 640 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 554 ms 1024 KB Partially correct
2 Partially correct 519 ms 1008 KB Partially correct
3 Correct 944 ms 640 KB Output is correct
4 Correct 792 ms 768 KB Output is correct
5 Correct 657 ms 644 KB Output is correct
6 Partially correct 570 ms 1016 KB Partially correct
7 Partially correct 588 ms 768 KB Partially correct
8 Correct 3 ms 648 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Partially correct 492 ms 1000 KB Partially correct
12 Partially correct 600 ms 768 KB Partially correct
13 Correct 915 ms 640 KB Output is correct
14 Correct 808 ms 768 KB Output is correct
15 Correct 607 ms 640 KB Output is correct
16 Partially correct 524 ms 828 KB Partially correct
17 Correct 620 ms 644 KB Output is correct
18 Partially correct 464 ms 1108 KB Partially correct
19 Partially correct 521 ms 992 KB Partially correct
20 Partially correct 549 ms 832 KB Partially correct
21 Correct 61 ms 892 KB Output is correct
22 Partially correct 75 ms 852 KB Partially correct
23 Partially correct 138 ms 920 KB Partially correct
24 Correct 6 ms 644 KB Output is correct
25 Correct 6 ms 896 KB Output is correct
26 Correct 5 ms 640 KB Output is correct
27 Correct 4 ms 648 KB Output is correct
28 Correct 2 ms 652 KB Output is correct
29 Correct 586 ms 640 KB Output is correct
30 Correct 552 ms 640 KB Output is correct
31 Correct 623 ms 648 KB Output is correct
32 Correct 574 ms 780 KB Output is correct
33 Correct 573 ms 776 KB Output is correct
34 Partially correct 341 ms 1008 KB Partially correct
35 Partially correct 444 ms 1008 KB Partially correct
36 Partially correct 550 ms 1060 KB Partially correct
37 Partially correct 455 ms 1000 KB Partially correct
38 Partially correct 540 ms 1008 KB Partially correct
39 Partially correct 566 ms 1008 KB Partially correct
40 Partially correct 570 ms 1008 KB Partially correct
41 Partially correct 502 ms 988 KB Partially correct
42 Partially correct 83 ms 1024 KB Partially correct
43 Partially correct 113 ms 788 KB Partially correct
44 Partially correct 128 ms 808 KB Partially correct
45 Partially correct 150 ms 980 KB Partially correct
46 Partially correct 336 ms 832 KB Partially correct
47 Partially correct 414 ms 792 KB Partially correct
48 Partially correct 87 ms 784 KB Partially correct
49 Partially correct 85 ms 1008 KB Partially correct