oj.uz

Submission #1009965

# Submission time Handle Problem Language Result Execution time Memory
1009965 2024-06-28T08:20:41 Z dimashhh Stations (IOI20_stations) C++17
76 / 100
 619 ms 1296 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 12;
vector<int> g[N];
int timer = 0,tin[N],tout[N],dd[N];
void dfs(int v,int pr = -1,int depth = 0){
    tin[v] = ++timer;
    dd[v] = depth;
    for(int to:g[v]){
        if(to == pr) continue;
        dfs(to,v,depth+1);
    }
    tout[v] = ++timer;
}
vector<int> label(int n, int k,vector<int> u,vector<int> v){
    vector<int> lab(n);
    timer = 0;
    for(int i = 0;i < n;i++){
        g[i].clear();
    }
    for(int i = 0;i < n - 1;i++){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    dfs(0);
    for(int i = 0;i < n;i++){
        if(dd[i] & 1){
            lab[i] = tout[i];
        }else{
            lab[i] = tin[i];
        }
    }
    return lab;
}
int find_next_station(int s, int t,vector<int> c){
    if((int)c.size() == 1){
        return c[0];
    }
    int m = (int)c.size();
    bool is_tin = false;
    if(s < c[0]){
        is_tin = 1;
    }
    if(is_tin){
        for(int i = 0;i < m - 1;i++){
            int ti = s + 1;
            if(i){
                ti = c[i - 1] + 1;
            }
            if(t >= ti && t <= c[i]){
                return c[i];
            }
        }
        return c.back();
    }else{
        for(int i = 1;i < m;i++){
            int ti = c[i],to = s - 1;
            if(i + 1 < m){
                to = c[i + 1] - 1;
            }
            if(t >= ti && t <= to){
                return c[i];
            }
        }
        return c[0];
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 932 KB Output is correct
2 Correct 309 ms 684 KB Output is correct
3 Correct 561 ms 684 KB Output is correct
4 Correct 418 ms 684 KB Output is correct
5 Correct 403 ms 688 KB Output is correct
6 Correct 304 ms 684 KB Output is correct
7 Correct 337 ms 688 KB Output is correct
8 Correct 1 ms 776 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Correct 385 ms 684 KB Output is correct
12 Correct 312 ms 1296 KB Output is correct
13 Correct 320 ms 932 KB Output is correct
14 Correct 271 ms 684 KB Output is correct
15 Correct 26 ms 768 KB Output is correct
16 Correct 38 ms 764 KB Output is correct
17 Correct 57 ms 684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 684 KB Output is correct
2 Correct 440 ms 684 KB Output is correct
3 Correct 384 ms 684 KB Output is correct
4 Correct 1 ms 764 KB Output is correct
5 Correct 1 ms 936 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 394 ms 684 KB Output is correct
8 Correct 619 ms 684 KB Output is correct
9 Correct 504 ms 684 KB Output is correct
10 Correct 400 ms 688 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 764 KB Output is correct
13 Correct 2 ms 788 KB Output is correct
14 Correct 2 ms 776 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 300 ms 684 KB Output is correct
17 Correct 308 ms 684 KB Output is correct
18 Correct 341 ms 684 KB Output is correct
19 Correct 299 ms 684 KB Output is correct
20 Correct 301 ms 696 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 337 ms 916 KB Partially correct
2 Partially correct 286 ms 924 KB Partially correct
3 Correct 591 ms 684 KB Output is correct
4 Correct 415 ms 684 KB Output is correct
5 Correct 313 ms 684 KB Output is correct
6 Partially correct 265 ms 684 KB Partially correct
7 Partially correct 246 ms 684 KB Partially correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Partially correct 242 ms 684 KB Partially correct
12 Partially correct 352 ms 684 KB Partially correct
13 Correct 539 ms 684 KB Output is correct
14 Correct 438 ms 684 KB Output is correct
15 Correct 356 ms 684 KB Output is correct
16 Partially correct 265 ms 684 KB Partially correct
17 Correct 365 ms 684 KB Output is correct
18 Partially correct 306 ms 800 KB Partially correct
19 Partially correct 297 ms 932 KB Partially correct
20 Partially correct 261 ms 684 KB Partially correct
21 Correct 26 ms 768 KB Output is correct
22 Partially correct 34 ms 776 KB Partially correct
23 Partially correct 47 ms 744 KB Partially correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 2 ms 776 KB Output is correct
26 Correct 2 ms 776 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 0 ms 768 KB Output is correct
29 Correct 313 ms 684 KB Output is correct
30 Correct 323 ms 684 KB Output is correct
31 Correct 309 ms 684 KB Output is correct
32 Correct 317 ms 684 KB Output is correct
33 Correct 341 ms 684 KB Output is correct
34 Partially correct 176 ms 912 KB Partially correct
35 Partially correct 267 ms 932 KB Partially correct
36 Partially correct 286 ms 684 KB Partially correct
37 Partially correct 308 ms 792 KB Partially correct
38 Partially correct 310 ms 1012 KB Partially correct
39 Partially correct 237 ms 796 KB Partially correct
40 Partially correct 263 ms 1052 KB Partially correct
41 Partially correct 313 ms 1184 KB Partially correct
42 Partially correct 27 ms 776 KB Partially correct
43 Partially correct 67 ms 684 KB Partially correct
44 Partially correct 75 ms 716 KB Partially correct
45 Partially correct 84 ms 716 KB Partially correct
46 Partially correct 192 ms 684 KB Partially correct
47 Partially correct 223 ms 684 KB Partially correct
48 Partially correct 37 ms 996 KB Partially correct
49 Partially correct 34 ms 768 KB Partially correct