oj.uz

Submission #578650

# Submission time Handle Problem Language Result Execution time Memory
578650 2022-06-17T12:40:06 Z perchuts Stations (IOI20_stations) C++17
100 / 100
 972 ms 1020 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

#include "stations.h"
vector<int>g[1001], labels;

int t = 0;

void dfs(int u,int p,bool entrada){
    if(entrada){
        labels[u] = t++;
    }
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u,entrada^1);
    }
    if(!entrada){
        labels[u] = t++;
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for(int i=0;i<n;++i){
        g[i].clear();
    }
    t = 0;
    for(int i=0;i<n-1;++i){
        g[u[i]].pb(v[i]);
        g[v[i]].pb(u[i]);
    }
    labels.resize(n);
    dfs(0,0,1);
    return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    int m = sz(c), idx = lower_bound(all(c),t)-begin(c);
    if(idx<m&&c[idx]==t)return t;//sou vizinho
    if(s>c[m-1]){//sou uma saida
        if(t>s||t<c[0])return c[0];//fora da subarvore
        return c[lower_bound(all(c),t) - begin(c) - 1];//ultimo cara que é menor
    }else{//sou uma entrada
        if(t>c[m-1]||t<s)return c[m-1];//fora da subarvore
        return c[lower_bound(all(c),t) - begin(c)];//primeiro cara que é maior
    }
}

// int main(){_
//     int n;cin>>n;
//     vector<int>u(n-1),v(n-1);
//     for(int i=0;i<n-1;++i){
//         cin>>u[i]>>v[i];
//     }    
//     vector<int>labels = label(n,n-1,u,v); 
//     // for(int i=1;i<=n;++i)printf("%d: %d\n",i-1,labels[i-1]);
//     cout<<find_next_station(1,3,{2,4})<<endl;
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 676 KB Output is correct
2 Correct 444 ms 652 KB Output is correct
3 Correct 972 ms 532 KB Output is correct
4 Correct 722 ms 416 KB Output is correct
5 Correct 598 ms 416 KB Output is correct
6 Correct 481 ms 548 KB Output is correct
7 Correct 479 ms 544 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 660 KB Output is correct
2 Correct 510 ms 532 KB Output is correct
3 Correct 891 ms 416 KB Output is correct
4 Correct 567 ms 420 KB Output is correct
5 Correct 504 ms 420 KB Output is correct
6 Correct 407 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 660 KB Output is correct
2 Correct 421 ms 656 KB Output is correct
3 Correct 851 ms 528 KB Output is correct
4 Correct 563 ms 416 KB Output is correct
5 Correct 506 ms 420 KB Output is correct
6 Correct 348 ms 656 KB Output is correct
7 Correct 430 ms 540 KB Output is correct
8 Correct 3 ms 500 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 556 ms 528 KB Output is correct
12 Correct 553 ms 756 KB Output is correct
13 Correct 447 ms 648 KB Output is correct
14 Correct 457 ms 532 KB Output is correct
15 Correct 46 ms 620 KB Output is correct
16 Correct 71 ms 544 KB Output is correct
17 Correct 112 ms 544 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 572 KB Output is correct
2 Correct 654 ms 524 KB Output is correct
3 Correct 636 ms 524 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 587 ms 536 KB Output is correct
8 Correct 896 ms 416 KB Output is correct
9 Correct 714 ms 524 KB Output is correct
10 Correct 655 ms 416 KB Output is correct
11 Correct 6 ms 492 KB Output is correct
12 Correct 6 ms 492 KB Output is correct
13 Correct 3 ms 488 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 618 ms 532 KB Output is correct
17 Correct 549 ms 528 KB Output is correct
18 Correct 527 ms 428 KB Output is correct
19 Correct 558 ms 528 KB Output is correct
20 Correct 608 ms 524 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 648 KB Output is correct
2 Correct 454 ms 544 KB Output is correct
3 Correct 729 ms 416 KB Output is correct
4 Correct 712 ms 416 KB Output is correct
5 Correct 659 ms 520 KB Output is correct
6 Correct 506 ms 544 KB Output is correct
7 Correct 519 ms 536 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 433 ms 528 KB Output is correct
12 Correct 575 ms 520 KB Output is correct
13 Correct 871 ms 524 KB Output is correct
14 Correct 785 ms 536 KB Output is correct
15 Correct 606 ms 532 KB Output is correct
16 Correct 447 ms 548 KB Output is correct
17 Correct 586 ms 420 KB Output is correct
18 Correct 442 ms 548 KB Output is correct
19 Correct 383 ms 760 KB Output is correct
20 Correct 449 ms 532 KB Output is correct
21 Correct 49 ms 500 KB Output is correct
22 Correct 69 ms 548 KB Output is correct
23 Correct 109 ms 700 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 5 ms 492 KB Output is correct
26 Correct 4 ms 504 KB Output is correct
27 Correct 4 ms 492 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 436 ms 532 KB Output is correct
30 Correct 447 ms 528 KB Output is correct
31 Correct 422 ms 628 KB Output is correct
32 Correct 517 ms 524 KB Output is correct
33 Correct 497 ms 420 KB Output is correct
34 Correct 253 ms 544 KB Output is correct
35 Correct 393 ms 772 KB Output is correct
36 Correct 453 ms 644 KB Output is correct
37 Correct 381 ms 648 KB Output is correct
38 Correct 341 ms 668 KB Output is correct
39 Correct 346 ms 656 KB Output is correct
40 Correct 438 ms 760 KB Output is correct
41 Correct 442 ms 1020 KB Output is correct
42 Correct 54 ms 620 KB Output is correct
43 Correct 117 ms 672 KB Output is correct
44 Correct 125 ms 664 KB Output is correct
45 Correct 170 ms 520 KB Output is correct
46 Correct 345 ms 548 KB Output is correct
47 Correct 280 ms 548 KB Output is correct
48 Correct 52 ms 676 KB Output is correct
49 Correct 64 ms 672 KB Output is correct