oj.uz

Submission #956621

# Submission time Handle Problem Language Result Execution time Memory
956621 2024-04-02T08:37:36 Z 12345678 Stations (IOI20_stations) C++17
52.3205 / 100
 598 ms 1436 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;
int in[nx], out[nx], cnt, pa;
vector<int> res, d[nx];

void dfs(int u, int p)
{
    in[u]=++cnt;
    for (auto v:d[u]) if (v!=p) dfs(v, u);
    out[u]=cnt;
}

int getin(int x)
{
    return x/1000;
}

int getout(int x)
{
    return x%1000;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    cnt=-1;
    for (int i=0; i<n; i++) d[i].clear();
    res.resize(n);
    for (int i=0; i<n-1; i++) d[u[i]].push_back(v[i]), d[v[i]].push_back(u[i]);
    dfs(0, 0);
    for (int i=0; i<n; i++) res[i]=1000*in[i]+out[i];
	return res;
}

int find_next_station(int s, int t, std::vector<int> c) {
    for (auto x:c) if (getin(x)<=getin(s)&&getout(s)<=getout(x)) pa=x;
    for (auto x:c) if (x!=pa&&getin(x)<=getin(t)&&getout(t)<=getout(x)) return x;
    return pa;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 928 KB Output is correct
2 Correct 247 ms 924 KB Output is correct
3 Correct 512 ms 684 KB Output is correct
4 Correct 403 ms 864 KB Output is correct
5 Correct 343 ms 844 KB Output is correct
6 Correct 288 ms 916 KB Output is correct
7 Correct 272 ms 692 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 3 ms 964 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 370 ms 940 KB Output is correct
12 Correct 291 ms 1172 KB Output is correct
13 Correct 332 ms 1420 KB Output is correct
14 Correct 317 ms 684 KB Output is correct
15 Correct 28 ms 768 KB Output is correct
16 Correct 36 ms 876 KB Output is correct
17 Correct 63 ms 884 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 684 KB Output is correct
2 Correct 412 ms 684 KB Output is correct
3 Correct 396 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 1 ms 764 KB Output is correct
7 Correct 370 ms 684 KB Output is correct
8 Correct 559 ms 684 KB Output is correct
9 Correct 431 ms 684 KB Output is correct
10 Correct 377 ms 684 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 3 ms 764 KB Output is correct
15 Correct 0 ms 772 KB Output is correct
16 Correct 369 ms 684 KB Output is correct
17 Correct 380 ms 684 KB Output is correct
18 Correct 312 ms 684 KB Output is correct
19 Correct 343 ms 684 KB Output is correct
20 Correct 368 ms 684 KB Output is correct

Subtask #5
26.3205 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 327 ms 920 KB Partially correct
2 Partially correct 317 ms 1064 KB Partially correct
3 Partially correct 589 ms 684 KB Partially correct
4 Partially correct 424 ms 684 KB Partially correct
5 Partially correct 362 ms 684 KB Partially correct
6 Partially correct 274 ms 912 KB Partially correct
7 Partially correct 281 ms 684 KB Partially correct
8 Partially correct 1 ms 764 KB Partially correct
9 Partially correct 2 ms 764 KB Partially correct
10 Partially correct 1 ms 768 KB Partially correct
11 Partially correct 275 ms 888 KB Partially correct
12 Partially correct 391 ms 852 KB Partially correct
13 Partially correct 598 ms 684 KB Partially correct
14 Partially correct 436 ms 684 KB Partially correct
15 Partially correct 379 ms 684 KB Partially correct
16 Partially correct 285 ms 684 KB Partially correct
17 Partially correct 464 ms 684 KB Partially correct
18 Partially correct 320 ms 1144 KB Partially correct
19 Partially correct 319 ms 1276 KB Partially correct
20 Partially correct 323 ms 684 KB Partially correct
21 Partially correct 39 ms 736 KB Partially correct
22 Partially correct 38 ms 1180 KB Partially correct
23 Partially correct 69 ms 1140 KB Partially correct
24 Partially correct 3 ms 768 KB Partially correct
25 Partially correct 4 ms 1016 KB Partially correct
26 Partially correct 3 ms 768 KB Partially correct
27 Partially correct 2 ms 768 KB Partially correct
28 Partially correct 2 ms 768 KB Partially correct
29 Partially correct 331 ms 684 KB Partially correct
30 Partially correct 343 ms 684 KB Partially correct
31 Partially correct 351 ms 684 KB Partially correct
32 Partially correct 327 ms 872 KB Partially correct
33 Partially correct 335 ms 684 KB Partially correct
34 Partially correct 213 ms 920 KB Partially correct
35 Partially correct 273 ms 1180 KB Partially correct
36 Partially correct 303 ms 1024 KB Partially correct
37 Partially correct 282 ms 1284 KB Partially correct
38 Partially correct 282 ms 1024 KB Partially correct
39 Partially correct 286 ms 1036 KB Partially correct
40 Partially correct 301 ms 1156 KB Partially correct
41 Partially correct 289 ms 1288 KB Partially correct
42 Partially correct 40 ms 1196 KB Partially correct
43 Partially correct 65 ms 964 KB Partially correct
44 Partially correct 89 ms 920 KB Partially correct
45 Partially correct 106 ms 928 KB Partially correct
46 Partially correct 209 ms 860 KB Partially correct
47 Partially correct 205 ms 896 KB Partially correct
48 Partially correct 42 ms 1208 KB Partially correct
49 Partially correct 45 ms 1436 KB Partially correct