oj.uz

Submission #563782

# Submission time Handle Problem Language Result Execution time Memory
563782 2022-05-18T06:20:04 Z Leo121 Stations (IOI20_stations) C++14
100 / 100
 803 ms 784 KB 
#include "stations.h"
#include <bits/stdc++.h>
#include <vector>

#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) for(int i = 0; i < int(n); ++ i)
#define for1(i, n) for(int i = 1; i <= int(n); ++ i)
#define pb push_back

using namespace std;

typedef vector<int> vi;

const int maxn = 1e3;
vi tree[maxn];
vi num;
int cnt;

void dfs(int u, int p, bool aux){
    if(!aux){
        num[u] = ++ cnt;
    }
    for(auto v : tree[u]){
        if(v == p){
            continue;
        }
        dfs(v, u, aux ^ 1);
    }
    if(aux){
        num[u] = ++ cnt;
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    num.clear();
	num.resize(n);
	for0(i, maxn){
        tree[i].clear();
	}
	for0(i, n - 1){
        tree[u[i]].pb(v[i]);
        tree[v[i]].pb(u[i]);
    }
    cnt = -1;
    dfs(0, 0, 0);
    return num;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if((int) c.size() == 1){
        return c[0];
	}
    int li = 1, ls = c.size() - 1, mitad;
    if(!s){
        while(li <= ls){
            mitad = (li + ls) / 2;
            if(t > c[mitad - 1] && t <= c[mitad]){
                return c[mitad];
            }
            if(t > c[mitad]){
                li = mitad + 1;
            }
            else{
                ls = mitad - 1;
            }
        }
        return c[0];
    }
    if(s > c[0]){
        ls --;
        while(li <= ls){
            mitad = (li + ls) / 2;
            if(t >= c[mitad] && t < c[mitad + 1]){
                return c[mitad];
            }
            if(t > c[mitad]){
                li = mitad + 1;
            }
            else{
                ls = mitad - 1;
            }
        }
        return (t >= c[(int) c.size() - 1] && t < s) ? c[(int) c.size() - 1] : c[0];
    }
    ls --;
    while(li <= ls){
        mitad = (li + ls) / 2;
        if(t <= c[mitad] && t > c[mitad - 1]){
            return c[mitad];
        }
        if(t > c[mitad]){
            li = mitad + 1;
        }
        else{
            ls = mitad - 1;
        }
    }
    return (t <= c[0] && t > s) ? c[0] : c[(int) c.size() - 1];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 784 KB Output is correct
2 Correct 405 ms 544 KB Output is correct
3 Correct 716 ms 416 KB Output is correct
4 Correct 548 ms 416 KB Output is correct
5 Correct 511 ms 524 KB Output is correct
6 Correct 390 ms 536 KB Output is correct
7 Correct 388 ms 652 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 588 KB Output is correct
2 Correct 459 ms 548 KB Output is correct
3 Correct 717 ms 416 KB Output is correct
4 Correct 572 ms 420 KB Output is correct
5 Correct 515 ms 420 KB Output is correct
6 Correct 328 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 720 KB Output is correct
2 Correct 346 ms 556 KB Output is correct
3 Correct 803 ms 520 KB Output is correct
4 Correct 630 ms 420 KB Output is correct
5 Correct 499 ms 548 KB Output is correct
6 Correct 379 ms 548 KB Output is correct
7 Correct 371 ms 548 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 500 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 501 ms 568 KB Output is correct
12 Correct 409 ms 644 KB Output is correct
13 Correct 384 ms 632 KB Output is correct
14 Correct 359 ms 656 KB Output is correct
15 Correct 43 ms 472 KB Output is correct
16 Correct 56 ms 600 KB Output is correct
17 Correct 80 ms 600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 416 KB Output is correct
2 Correct 603 ms 420 KB Output is correct
3 Correct 456 ms 528 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 4 ms 488 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 513 ms 524 KB Output is correct
8 Correct 755 ms 416 KB Output is correct
9 Correct 577 ms 524 KB Output is correct
10 Correct 474 ms 524 KB Output is correct
11 Correct 5 ms 500 KB Output is correct
12 Correct 6 ms 492 KB Output is correct
13 Correct 5 ms 492 KB Output is correct
14 Correct 3 ms 500 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 378 ms 532 KB Output is correct
17 Correct 393 ms 528 KB Output is correct
18 Correct 437 ms 532 KB Output is correct
19 Correct 443 ms 444 KB Output is correct
20 Correct 437 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 656 KB Output is correct
2 Correct 343 ms 544 KB Output is correct
3 Correct 645 ms 416 KB Output is correct
4 Correct 520 ms 420 KB Output is correct
5 Correct 500 ms 528 KB Output is correct
6 Correct 410 ms 544 KB Output is correct
7 Correct 391 ms 536 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 380 ms 656 KB Output is correct
12 Correct 415 ms 544 KB Output is correct
13 Correct 734 ms 420 KB Output is correct
14 Correct 525 ms 416 KB Output is correct
15 Correct 460 ms 420 KB Output is correct
16 Correct 381 ms 528 KB Output is correct
17 Correct 476 ms 540 KB Output is correct
18 Correct 353 ms 528 KB Output is correct
19 Correct 379 ms 548 KB Output is correct
20 Correct 370 ms 548 KB Output is correct
21 Correct 56 ms 472 KB Output is correct
22 Correct 66 ms 624 KB Output is correct
23 Correct 98 ms 532 KB Output is correct
24 Correct 5 ms 488 KB Output is correct
25 Correct 5 ms 500 KB Output is correct
26 Correct 4 ms 492 KB Output is correct
27 Correct 4 ms 492 KB Output is correct
28 Correct 2 ms 500 KB Output is correct
29 Correct 454 ms 420 KB Output is correct
30 Correct 386 ms 420 KB Output is correct
31 Correct 434 ms 420 KB Output is correct
32 Correct 392 ms 416 KB Output is correct
33 Correct 417 ms 528 KB Output is correct
34 Correct 271 ms 660 KB Output is correct
35 Correct 333 ms 596 KB Output is correct
36 Correct 361 ms 652 KB Output is correct
37 Correct 367 ms 548 KB Output is correct
38 Correct 348 ms 608 KB Output is correct
39 Correct 365 ms 628 KB Output is correct
40 Correct 374 ms 548 KB Output is correct
41 Correct 364 ms 776 KB Output is correct
42 Correct 61 ms 572 KB Output is correct
43 Correct 91 ms 528 KB Output is correct
44 Correct 106 ms 524 KB Output is correct
45 Correct 134 ms 548 KB Output is correct
46 Correct 252 ms 532 KB Output is correct
47 Correct 229 ms 528 KB Output is correct
48 Correct 54 ms 676 KB Output is correct
49 Correct 56 ms 676 KB Output is correct