oj.uz

Submission #615915

# Submission time Handle Problem Language Result Execution time Memory
615915 2022-07-31T14:40:58 Z eNGy Stations (IOI20_stations) C++17
100 / 100
 986 ms 740 KB 
#include <bits/stdc++.h>
#define con(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)
#define ll long long
#define f first
#define s second
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;

void dfs(int n, int p, int d, int &e, vector<int> &L, vector<vector<int>> &G){
    if(d%2 == 0) L[n] = e++;
    for(int v: G[n]){
        if(v != p){
            dfs(v, n, d+1, e, L, G);
        }
    }
    if(d%2 != 0) L[n] = e++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
    vector<vector<int>> G(n);
    for(int i=0; i<n-1; i++){
		G[u[i]].pb(v[i]);
		G[v[i]].pb(u[i]);
	}

    vector<int> L(n);
    int e = 0;

    dfs(0, -1, 0, e, L, G);

    //for(int l: L) cout << l << ' '; cout << endl;

    return L;
}

int find_next_station(int s, int t, std::vector<int> c){
    int N = c.size();
    if(N == 1) return c[0];

    pair<int, int> S;
    vector<pair<int, int>> C(N);

    if(c[0] > s){
        // s open

        C[N-1] = {-1, -1};

        S.s = c[N-2];
        S.f = s;

        if(t < S.f || t > S.s)
            return c[N-1];

        for(int i=N-2; i>0; i--){
            C[i].s = c[i];
            C[i].f = c[i-1] + 1;
        }

        C[0].f = s + 1;
        C[0].s = c[0];

    }else{
        // s close
        C[0] = {-1, -1};

        S.f = c[1];
        S.s = s;

        if(t < S.f || t > S.s)
            return c[0];

        for(int i=1; i<N-1; i++){
            C[i].f = c[i];
            C[i].s = c[i+1] - 1;
        }

        C[N-1].f = c[N-1];
        C[N-1].s = s - 1;

    }

    //cout << S.f << ' ' << S.s << endl;
    for(int i=0; i<N; i++){
        //cout << C[i].f << ' ' << C[i].s << endl;
        if(C[i].f <= t && t <= C[i].s)
            return c[i];
    }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:47:31: warning: control reaches end of non-void function [-Wreturn-type]
   47 |     vector<pair<int, int>> C(N);
      |                               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 740 KB Output is correct
2 Correct 397 ms 632 KB Output is correct
3 Correct 757 ms 500 KB Output is correct
4 Correct 645 ms 416 KB Output is correct
5 Correct 535 ms 420 KB Output is correct
6 Correct 454 ms 544 KB Output is correct
7 Correct 521 ms 552 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 544 KB Output is correct
2 Correct 476 ms 500 KB Output is correct
3 Correct 840 ms 420 KB Output is correct
4 Correct 671 ms 504 KB Output is correct
5 Correct 626 ms 500 KB Output is correct
6 Correct 420 ms 548 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 636 KB Output is correct
2 Correct 418 ms 548 KB Output is correct
3 Correct 986 ms 420 KB Output is correct
4 Correct 650 ms 508 KB Output is correct
5 Correct 648 ms 416 KB Output is correct
6 Correct 420 ms 620 KB Output is correct
7 Correct 434 ms 628 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 606 ms 416 KB Output is correct
12 Correct 422 ms 708 KB Output is correct
13 Correct 446 ms 672 KB Output is correct
14 Correct 355 ms 508 KB Output is correct
15 Correct 52 ms 496 KB Output is correct
16 Correct 66 ms 544 KB Output is correct
17 Correct 106 ms 548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 464 KB Output is correct
2 Correct 661 ms 508 KB Output is correct
3 Correct 572 ms 504 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 2 ms 500 KB Output is correct
7 Correct 575 ms 500 KB Output is correct
8 Correct 906 ms 508 KB Output is correct
9 Correct 693 ms 504 KB Output is correct
10 Correct 563 ms 416 KB Output is correct
11 Correct 4 ms 500 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 4 ms 492 KB Output is correct
14 Correct 3 ms 488 KB Output is correct
15 Correct 1 ms 500 KB Output is correct
16 Correct 504 ms 504 KB Output is correct
17 Correct 556 ms 544 KB Output is correct
18 Correct 528 ms 500 KB Output is correct
19 Correct 492 ms 508 KB Output is correct
20 Correct 412 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 676 KB Output is correct
2 Correct 372 ms 548 KB Output is correct
3 Correct 778 ms 504 KB Output is correct
4 Correct 664 ms 504 KB Output is correct
5 Correct 451 ms 500 KB Output is correct
6 Correct 344 ms 676 KB Output is correct
7 Correct 443 ms 512 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 451 ms 500 KB Output is correct
12 Correct 447 ms 508 KB Output is correct
13 Correct 760 ms 504 KB Output is correct
14 Correct 732 ms 416 KB Output is correct
15 Correct 617 ms 504 KB Output is correct
16 Correct 351 ms 544 KB Output is correct
17 Correct 625 ms 500 KB Output is correct
18 Correct 457 ms 628 KB Output is correct
19 Correct 408 ms 624 KB Output is correct
20 Correct 424 ms 548 KB Output is correct
21 Correct 57 ms 444 KB Output is correct
22 Correct 64 ms 560 KB Output is correct
23 Correct 84 ms 544 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 6 ms 516 KB Output is correct
26 Correct 6 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 474 ms 504 KB Output is correct
30 Correct 550 ms 504 KB Output is correct
31 Correct 537 ms 416 KB Output is correct
32 Correct 523 ms 420 KB Output is correct
33 Correct 415 ms 416 KB Output is correct
34 Correct 290 ms 636 KB Output is correct
35 Correct 387 ms 736 KB Output is correct
36 Correct 462 ms 616 KB Output is correct
37 Correct 380 ms 592 KB Output is correct
38 Correct 419 ms 596 KB Output is correct
39 Correct 376 ms 732 KB Output is correct
40 Correct 410 ms 724 KB Output is correct
41 Correct 439 ms 636 KB Output is correct
42 Correct 56 ms 548 KB Output is correct
43 Correct 106 ms 544 KB Output is correct
44 Correct 135 ms 504 KB Output is correct
45 Correct 147 ms 504 KB Output is correct
46 Correct 315 ms 500 KB Output is correct
47 Correct 260 ms 504 KB Output is correct
48 Correct 52 ms 600 KB Output is correct
49 Correct 53 ms 732 KB Output is correct