oj.uz

Submission #306819

# Submission time Handle Problem Language Result Execution time Memory
306819 2020-09-26T10:34:11 Z nicolaalexandra Stations (IOI20_stations) C++14
76 / 100
 1055 ms 1168 KB 
#include <bits/stdc++.h>
#include "stations.h"
#define DIM 1010
using namespace std;

vector <int> L[DIM];
int viz[DIM],level[DIM];
pair <int,int> poz[DIM];
int idx;

void dfs (int nod){

    viz[nod] = 1;
    poz[nod].first = ++idx;
    for (auto vecin : L[nod])
        if (!viz[vecin]){
            level[vecin] = 1 + level[nod];
            dfs (vecin);
        }
    poz[nod].second = ++idx;
}

vector <int> label (int n, int k, vector <int> u, vector <int> v){
    int i;

    for (i=0;i<n;i++)
        L[i].clear();

    for (i=0;i<n-1;i++){
        int x = u[i], y = v[i];
        L[x].push_back(y);
        L[y].push_back(x);
    }

    memset (viz,0,sizeof viz);
    memset (level,0,sizeof level);
    memset (poz,0,sizeof poz);
    idx = -1;

    dfs (0);

    vector <int> labels;
    for (i=0;i<n;i++){
        if (level[i] % 2 == 0)
            labels.push_back(poz[i].first);
        else labels.push_back(poz[i].second);
    }

    return labels;

}

int find_next_station (int x, int y, vector <int> v){

    /// mai intai vad daca se afla pe un nivel par sau impar

    int ok = 0;
    for (auto it : v)
        if (it < x){
            ok = 1;
            break;
        }

    if (!ok){ /// labelul x inseamna de fapt un inceput de interval

        if (y < x)
            return v.back();

        for (auto it : v)
            if (y <= it)
                return it;

        return v.back();

    } else {

        if (y > x)
            return v.front();

        for (int i=v.size()-1;i>=0;i--)
            if (y >= v[i])
                return v[i];

        return v.front();
    }

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 500 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 4 ms 476 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 563 ms 1008 KB Output is correct
2 Correct 478 ms 908 KB Output is correct
3 Correct 917 ms 1024 KB Output is correct
4 Correct 644 ms 860 KB Output is correct
5 Correct 636 ms 864 KB Output is correct
6 Correct 514 ms 1008 KB Output is correct
7 Correct 498 ms 780 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 580 ms 1168 KB Output is correct
12 Correct 454 ms 768 KB Output is correct
13 Correct 459 ms 888 KB Output is correct
14 Correct 468 ms 768 KB Output is correct
15 Correct 60 ms 768 KB Output is correct
16 Correct 71 ms 1024 KB Output is correct
17 Correct 110 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 860 KB Output is correct
2 Correct 737 ms 1008 KB Output is correct
3 Correct 636 ms 1160 KB Output is correct
4 Correct 3 ms 864 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 868 KB Output is correct
7 Correct 598 ms 768 KB Output is correct
8 Correct 998 ms 768 KB Output is correct
9 Correct 673 ms 1032 KB Output is correct
10 Correct 599 ms 860 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 7 ms 872 KB Output is correct
13 Correct 6 ms 768 KB Output is correct
14 Correct 4 ms 768 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 548 ms 864 KB Output is correct
17 Correct 600 ms 776 KB Output is correct
18 Correct 584 ms 1024 KB Output is correct
19 Correct 503 ms 792 KB Output is correct
20 Correct 541 ms 808 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 613 ms 1012 KB Partially correct
2 Partially correct 458 ms 1000 KB Partially correct
3 Correct 1055 ms 768 KB Output is correct
4 Correct 890 ms 768 KB Output is correct
5 Correct 588 ms 768 KB Output is correct
6 Partially correct 430 ms 768 KB Partially correct
7 Partially correct 494 ms 796 KB Partially correct
8 Correct 3 ms 868 KB Output is correct
9 Correct 5 ms 996 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Partially correct 483 ms 792 KB Partially correct
12 Partially correct 551 ms 796 KB Partially correct
13 Correct 914 ms 864 KB Output is correct
14 Correct 735 ms 864 KB Output is correct
15 Correct 572 ms 868 KB Output is correct
16 Partially correct 448 ms 804 KB Partially correct
17 Correct 594 ms 1040 KB Output is correct
18 Partially correct 537 ms 884 KB Partially correct
19 Partially correct 490 ms 984 KB Partially correct
20 Partially correct 610 ms 1024 KB Partially correct
21 Correct 60 ms 768 KB Output is correct
22 Partially correct 75 ms 828 KB Partially correct
23 Partially correct 113 ms 768 KB Partially correct
24 Correct 7 ms 768 KB Output is correct
25 Correct 6 ms 768 KB Output is correct
26 Correct 5 ms 768 KB Output is correct
27 Correct 5 ms 768 KB Output is correct
28 Correct 3 ms 868 KB Output is correct
29 Correct 559 ms 864 KB Output is correct
30 Correct 550 ms 768 KB Output is correct
31 Correct 525 ms 768 KB Output is correct
32 Correct 730 ms 768 KB Output is correct
33 Correct 482 ms 896 KB Output is correct
34 Partially correct 338 ms 1088 KB Partially correct
35 Partially correct 449 ms 1048 KB Partially correct
36 Partially correct 469 ms 984 KB Partially correct
37 Partially correct 509 ms 888 KB Partially correct
38 Partially correct 500 ms 980 KB Partially correct
39 Partially correct 543 ms 1000 KB Partially correct
40 Partially correct 466 ms 992 KB Partially correct
41 Partially correct 525 ms 892 KB Partially correct
42 Partially correct 59 ms 928 KB Partially correct
43 Partially correct 109 ms 800 KB Partially correct
44 Partially correct 131 ms 768 KB Partially correct
45 Partially correct 228 ms 984 KB Partially correct
46 Partially correct 392 ms 768 KB Partially correct
47 Partially correct 298 ms 792 KB Partially correct
48 Partially correct 88 ms 1024 KB Partially correct
49 Partially correct 55 ms 1008 KB Partially correct