oj.uz

Submission #398255

# Submission time Handle Problem Language Result Execution time Memory
398255 2021-05-04T02:33:37 Z Everule Stations (IOI20_stations) C++17
76 / 100
 1142 ms 984 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
    vector<vector<int>> adj(n);
    for(int i=0;i<n-1;i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    vector<int> tin(n), tout(n), dep(n);
    int t = 0;
    function<void(int,int)> dfs = [&](int u,int p){
        tin[u] = t++;
        for(auto &v : adj[u]){
            if(v == p) continue;
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
        tout[u] = t++;
    };
    dfs(0, 0);
    for(int i=0;i<n;i++){
        if(dep[i] % 2 == 0){
            labels[i] = tin[i];
        }
        else{
            labels[i] = tout[i];
        }
    }
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if(c.size() == 1) return c[0];
    sort(c.begin(), c.end());
	if(c[0] < s){
        if(t < c[1] || t > s){
            return c[0];
        }
        for(int i=c.size()-1;i>0;--i){
            if(c[i] <= t) return c[i];
        }
    }
    else{
        reverse(c.begin(), c.end());
        if(t > c[1] || t < s){
            return c[0];
        }
        for(int i=c.size()-1;i>0;--i){
            if(c[i] >= t) return c[i];
        }
    }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 464 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 5 ms 328 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 667 ms 644 KB Output is correct
2 Correct 525 ms 620 KB Output is correct
3 Correct 1142 ms 400 KB Output is correct
4 Correct 958 ms 492 KB Output is correct
5 Correct 721 ms 488 KB Output is correct
6 Correct 544 ms 604 KB Output is correct
7 Correct 536 ms 624 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 5 ms 452 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 737 ms 400 KB Output is correct
12 Correct 593 ms 688 KB Output is correct
13 Correct 609 ms 728 KB Output is correct
14 Correct 476 ms 632 KB Output is correct
15 Correct 50 ms 420 KB Output is correct
16 Correct 107 ms 544 KB Output is correct
17 Correct 144 ms 592 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 488 KB Output is correct
2 Correct 931 ms 476 KB Output is correct
3 Correct 672 ms 400 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 7 ms 492 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 724 ms 400 KB Output is correct
8 Correct 1109 ms 400 KB Output is correct
9 Correct 762 ms 488 KB Output is correct
10 Correct 621 ms 400 KB Output is correct
11 Correct 5 ms 476 KB Output is correct
12 Correct 5 ms 472 KB Output is correct
13 Correct 6 ms 480 KB Output is correct
14 Correct 5 ms 480 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 647 ms 492 KB Output is correct
17 Correct 500 ms 548 KB Output is correct
18 Correct 617 ms 528 KB Output is correct
19 Correct 679 ms 400 KB Output is correct
20 Correct 658 ms 492 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 585 ms 652 KB Partially correct
2 Partially correct 516 ms 612 KB Partially correct
3 Correct 1035 ms 544 KB Output is correct
4 Correct 936 ms 492 KB Output is correct
5 Correct 635 ms 492 KB Output is correct
6 Partially correct 639 ms 744 KB Partially correct
7 Partially correct 580 ms 624 KB Partially correct
8 Correct 4 ms 472 KB Output is correct
9 Correct 6 ms 472 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Partially correct 608 ms 644 KB Partially correct
12 Partially correct 572 ms 564 KB Partially correct
13 Correct 1132 ms 472 KB Output is correct
14 Correct 753 ms 492 KB Output is correct
15 Correct 732 ms 400 KB Output is correct
16 Partially correct 591 ms 616 KB Partially correct
17 Correct 732 ms 400 KB Output is correct
18 Partially correct 526 ms 820 KB Partially correct
19 Partially correct 589 ms 864 KB Partially correct
20 Partially correct 521 ms 528 KB Partially correct
21 Correct 71 ms 420 KB Output is correct
22 Partially correct 100 ms 532 KB Partially correct
23 Partially correct 163 ms 600 KB Partially correct
24 Correct 8 ms 472 KB Output is correct
25 Correct 6 ms 472 KB Output is correct
26 Correct 7 ms 472 KB Output is correct
27 Correct 5 ms 556 KB Output is correct
28 Correct 2 ms 480 KB Output is correct
29 Correct 600 ms 492 KB Output is correct
30 Correct 692 ms 552 KB Output is correct
31 Correct 560 ms 400 KB Output is correct
32 Correct 635 ms 488 KB Output is correct
33 Correct 584 ms 496 KB Output is correct
34 Partially correct 413 ms 616 KB Partially correct
35 Partially correct 407 ms 728 KB Partially correct
36 Partially correct 586 ms 700 KB Partially correct
37 Partially correct 436 ms 644 KB Partially correct
38 Partially correct 633 ms 648 KB Partially correct
39 Partially correct 544 ms 680 KB Partially correct
40 Partially correct 616 ms 680 KB Partially correct
41 Partially correct 580 ms 984 KB Partially correct
42 Partially correct 72 ms 528 KB Partially correct
43 Partially correct 120 ms 592 KB Partially correct
44 Partially correct 192 ms 488 KB Partially correct
45 Partially correct 276 ms 496 KB Partially correct
46 Partially correct 437 ms 584 KB Partially correct
47 Partially correct 438 ms 672 KB Partially correct
48 Partially correct 82 ms 484 KB Partially correct
49 Partially correct 80 ms 528 KB Partially correct