oj.uz

Submission #1064118

# Submission time Handle Problem Language Result Execution time Memory
1064118 2024-08-18T09:24:05 Z new_acc Stations (IOI20_stations) C++14
100 / 100
 657 ms 1196 KB 
#include "stations.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
const int N=1e3+10;
vi graf[N];
int val[N],li,kol[N];
void dfs(int v,int o){
    li++;
    if(!kol[v]) val[v]=li;
    for(auto u:graf[v]){
        if(u==o) continue;
        kol[u]=kol[v]^1;
        dfs(u,v);
    }
    li++;
    if(kol[v]) val[v]=li;
}
vi label(int n, int k, vi u,vi v) {
    for(int i=0;i<n;i++) graf[i].clear(),kol[i]=0,val[i]=0;
    li=0;
    for(int i=0;i<n-1;i++)
        graf[u[i]].push_back(v[i]),graf[v[i]].push_back(u[i]);
    dfs(0,0);
    vector<pair<int,int>> pom;
    for(int i=0;i<n;i++) pom.push_back({val[i],i});
    sort(pom.begin(),pom.end());
    vi labels(n);
    for(int i=0;i<n;i++) labels[pom[i].se]=i;
    return labels;
}

int find_next_station(int s,int t,vi c) {
    if(c.size()==1) return c[0];
    if(c[0]>s){
        // pre
        if(s==0){
            for(auto u:c){
                if(u>=t) return u;
            }
            return 0;
        }
        if(t>=s and t<=c[c.size()-2]){
            for(auto u:c){
                if(u>=t) return u;
            }
            return 0;
        }else return c[c.size()-1];
    }else{
        if(t>c[0] and t<=s){
            int ost=c[0];
            for(int i=1;i<(int)c.size();i++){
                if(t>=c[i]) ost=c[i];
            }
            return ost;
        }else return c[0];
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 684 KB Output is correct
2 Correct 291 ms 684 KB Output is correct
3 Correct 573 ms 684 KB Output is correct
4 Correct 417 ms 684 KB Output is correct
5 Correct 332 ms 684 KB Output is correct
6 Correct 323 ms 684 KB Output is correct
7 Correct 283 ms 684 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 764 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 684 KB Output is correct
2 Correct 351 ms 684 KB Output is correct
3 Correct 598 ms 684 KB Output is correct
4 Correct 440 ms 684 KB Output is correct
5 Correct 416 ms 684 KB Output is correct
6 Correct 339 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 684 KB Output is correct
2 Correct 316 ms 684 KB Output is correct
3 Correct 657 ms 684 KB Output is correct
4 Correct 466 ms 684 KB Output is correct
5 Correct 373 ms 684 KB Output is correct
6 Correct 339 ms 684 KB Output is correct
7 Correct 283 ms 936 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 396 ms 796 KB Output is correct
12 Correct 296 ms 792 KB Output is correct
13 Correct 302 ms 792 KB Output is correct
14 Correct 291 ms 684 KB Output is correct
15 Correct 28 ms 768 KB Output is correct
16 Correct 39 ms 768 KB Output is correct
17 Correct 69 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 684 KB Output is correct
2 Correct 462 ms 684 KB Output is correct
3 Correct 421 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 776 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 393 ms 684 KB Output is correct
8 Correct 620 ms 936 KB Output is correct
9 Correct 446 ms 688 KB Output is correct
10 Correct 395 ms 684 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 776 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 2 ms 772 KB Output is correct
16 Correct 331 ms 684 KB Output is correct
17 Correct 314 ms 684 KB Output is correct
18 Correct 298 ms 684 KB Output is correct
19 Correct 355 ms 704 KB Output is correct
20 Correct 305 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 684 KB Output is correct
2 Correct 289 ms 684 KB Output is correct
3 Correct 598 ms 684 KB Output is correct
4 Correct 487 ms 684 KB Output is correct
5 Correct 408 ms 680 KB Output is correct
6 Correct 304 ms 684 KB Output is correct
7 Correct 304 ms 684 KB Output is correct
8 Correct 2 ms 772 KB Output is correct
9 Correct 1 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 286 ms 800 KB Output is correct
12 Correct 313 ms 680 KB Output is correct
13 Correct 598 ms 688 KB Output is correct
14 Correct 459 ms 684 KB Output is correct
15 Correct 394 ms 684 KB Output is correct
16 Correct 323 ms 684 KB Output is correct
17 Correct 401 ms 684 KB Output is correct
18 Correct 295 ms 788 KB Output is correct
19 Correct 312 ms 792 KB Output is correct
20 Correct 308 ms 684 KB Output is correct
21 Correct 26 ms 812 KB Output is correct
22 Correct 35 ms 716 KB Output is correct
23 Correct 57 ms 768 KB Output is correct
24 Correct 3 ms 768 KB Output is correct
25 Correct 2 ms 764 KB Output is correct
26 Correct 2 ms 776 KB Output is correct
27 Correct 1 ms 764 KB Output is correct
28 Correct 1 ms 764 KB Output is correct
29 Correct 343 ms 684 KB Output is correct
30 Correct 331 ms 684 KB Output is correct
31 Correct 351 ms 684 KB Output is correct
32 Correct 349 ms 684 KB Output is correct
33 Correct 342 ms 684 KB Output is correct
34 Correct 193 ms 684 KB Output is correct
35 Correct 311 ms 1196 KB Output is correct
36 Correct 315 ms 1188 KB Output is correct
37 Correct 323 ms 792 KB Output is correct
38 Correct 304 ms 788 KB Output is correct
39 Correct 333 ms 932 KB Output is correct
40 Correct 280 ms 932 KB Output is correct
41 Correct 313 ms 796 KB Output is correct
42 Correct 32 ms 768 KB Output is correct
43 Correct 68 ms 684 KB Output is correct
44 Correct 83 ms 736 KB Output is correct
45 Correct 90 ms 760 KB Output is correct
46 Correct 189 ms 948 KB Output is correct
47 Correct 230 ms 684 KB Output is correct
48 Correct 46 ms 768 KB Output is correct
49 Correct 33 ms 768 KB Output is correct