oj.uz

Submission #964631

# Submission time Handle Problem Language Result Execution time Memory
964631 2024-04-17T08:39:49 Z irmuun Stations (IOI20_stations) C++17
76 / 100
 605 ms 1708 KB 
#include<bits/stdc++.h>
#include "stations.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=1e3+5;
vector<int>adj[N],tin(N),tout(N),dep(N);
int cur=0;
void dfs(int x,int p){
    tin[x]=cur++;
    for(auto y:adj[x]){
        if(y!=p){
            dep[y]=dep[x]+1;
            dfs(y,x);
        }
    }
    tout[x]=cur++;
}

vector<int>label(int n,int k,vector<int>u,vector<int>v){
    cur=0;
    for(int i=0;i<n;i++){
        adj[i].clear();
    }
    for(int i=0;i<n-1;i++){
        adj[u[i]].pb(v[i]);
        adj[v[i]].pb(u[i]);
    }
    dfs(0,-1);
    vector<int>l(n);
    for(int i=0;i<n;i++){
        if(dep[i]%2==0){
            l[i]=tin[i];
        }
        else{
            l[i]=tout[i];
        }
    }
    return l;
}
 
int find_next_station(int s,int t,vector<int>c){
    if(s<c[0]){
        int l=s+1;
        for(int i=0;i<(int)c.size()-1;i++){
            if(l<=t&&t<=c[i]){
                return c[i];
            }
            l=c[i]+1;
        }
        return c.back();
    }
    else{
        int r=s-1;
        for(int i=(int)c.size()-1;i>0;i--){
            if(c[i]<=t&&t<=r){
                return c[i];
            }
            r=c[i]-1;
        }
        return c[0];
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 576 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 2 ms 540 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 326 ms 928 KB Output is correct
2 Correct 307 ms 932 KB Output is correct
3 Correct 561 ms 688 KB Output is correct
4 Correct 429 ms 688 KB Output is correct
5 Correct 391 ms 684 KB Output is correct
6 Correct 297 ms 928 KB Output is correct
7 Correct 271 ms 684 KB Output is 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 Correct 364 ms 684 KB Output is correct
12 Correct 304 ms 1180 KB Output is correct
13 Correct 302 ms 1164 KB Output is correct
14 Correct 312 ms 684 KB Output is correct
15 Correct 44 ms 1020 KB Output is correct
16 Correct 39 ms 928 KB Output is correct
17 Correct 72 ms 884 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 728 KB Output is correct
2 Correct 453 ms 684 KB Output is correct
3 Correct 397 ms 684 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 3 ms 764 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 399 ms 936 KB Output is correct
8 Correct 603 ms 684 KB Output is correct
9 Correct 476 ms 936 KB Output is correct
10 Correct 431 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 4 ms 764 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 343 ms 684 KB Output is correct
17 Correct 378 ms 808 KB Output is correct
18 Correct 340 ms 868 KB Output is correct
19 Correct 337 ms 684 KB Output is correct
20 Correct 313 ms 692 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 340 ms 928 KB Partially correct
2 Partially correct 287 ms 928 KB Partially correct
3 Correct 575 ms 960 KB Output is correct
4 Correct 428 ms 972 KB Output is correct
5 Correct 368 ms 684 KB Output is correct
6 Partially correct 325 ms 932 KB Partially correct
7 Partially correct 315 ms 684 KB Partially correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 3 ms 808 KB Output is correct
10 Correct 1 ms 764 KB Output is correct
11 Partially correct 319 ms 1128 KB Partially correct
12 Partially correct 376 ms 1028 KB Partially correct
13 Correct 571 ms 1108 KB Output is correct
14 Correct 459 ms 684 KB Output is correct
15 Correct 417 ms 684 KB Output is correct
16 Partially correct 329 ms 948 KB Partially correct
17 Correct 372 ms 684 KB Output is correct
18 Partially correct 317 ms 1028 KB Partially correct
19 Partially correct 329 ms 1552 KB Partially correct
20 Partially correct 314 ms 684 KB Partially correct
21 Correct 33 ms 1020 KB Output is correct
22 Partially correct 42 ms 1452 KB Partially correct
23 Partially correct 70 ms 1460 KB Partially correct
24 Correct 5 ms 1024 KB Output is correct
25 Correct 3 ms 804 KB Output is correct
26 Correct 3 ms 768 KB Output is correct
27 Correct 3 ms 764 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 357 ms 684 KB Output is correct
30 Correct 349 ms 684 KB Output is correct
31 Correct 351 ms 684 KB Output is correct
32 Correct 340 ms 684 KB Output is correct
33 Correct 365 ms 684 KB Output is correct
34 Partially correct 224 ms 912 KB Partially correct
35 Partially correct 318 ms 1188 KB Partially correct
36 Partially correct 325 ms 1040 KB Partially correct
37 Partially correct 322 ms 1164 KB Partially correct
38 Partially correct 316 ms 1156 KB Partially correct
39 Partially correct 307 ms 1168 KB Partially correct
40 Partially correct 330 ms 1184 KB Partially correct
41 Partially correct 323 ms 1152 KB Partially correct
42 Partially correct 38 ms 856 KB Partially correct
43 Partially correct 73 ms 880 KB Partially correct
44 Partially correct 101 ms 1144 KB Partially correct
45 Partially correct 127 ms 900 KB Partially correct
46 Partially correct 216 ms 864 KB Partially correct
47 Partially correct 221 ms 896 KB Partially correct
48 Partially correct 38 ms 1244 KB Partially correct
49 Partially correct 33 ms 1708 KB Partially correct