oj.uz

Submission #432819

# Submission time Handle Problem Language Result Execution time Memory
432819 2021-06-18T13:32:02 Z TryMax Stations (IOI20_stations) C++17
52.3244 / 100
 979 ms 94800 KB 
#include "stations.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "stub.cpp"
#endif // LOCAL

#define f first
#define s second
#define pb push_back

using namespace std;

const int N = 2e6 + 10;

int sz[N], p[N], timer, was[N];
vector<int> a[N];

int cypher(int a, int b){
    return a * 1000 + (b - 1);
}

pair<int, int> decyper(int num){
    return {num / 1000, num % 1000 + 1};
}

void dfs(int u, int pr){
    sz[u] = 1;
    p[u] = timer++;
    for(auto v : a[u])
        if(pr != v){
            dfs(v, u);
            sz[u] += sz[v];
        }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<int> lb;
    lb.resize(n);
    timer = 0;
    for(int i= 0; i < n; ++i)
        a[i].clear();
    for(int i = 0; i < n - 1; ++i){
        a[u[i]].pb(v[i]);
        a[v[i]].pb(u[i]);
    }
    dfs(0, -1);
//    for(int i = 1; i < n; ++i)
//        if(p[i] == 0)
//            exit(1);
    for(int i = 0; i < n; ++i)
        lb[i] = cypher(p[i], sz[i]);
//    exit(0);
    return lb;
}

int find_next_station(int s, int t, vector<int> c) {
    pair<int, int> s1 = decyper(s);
    pair<int, int> t1 = decyper(t);
    int pr = 0;
    vector<pair<int, int>> p;
    for(auto v : c){
        pair<int, int> c1 = decyper(v);
        if(c1.f <= s1.f)
            pr = v;
        p.pb(c1);
    }
    sort(p.begin(), p.end());
//    cout << s1.f << " " << s1.s << endl;
//    cout << t1.f << " " << t1.s << endl;
    if(t1.f < s1.f || t1.f >= s1.f + s1.s)
        return pr;
//    cout << 1 << endl;
    for(int i = p.size() - 1; i >= 0; --i)
        if(t1.f >= p[i].f)
            return cypher(p[i].f, p[i].s);
    return cypher(p[0].f, p[0].s);
}
/*
1
7 1000000
0 1
0 2
1 3
1 4
2 5
2 6
2
2 0 1
1 3 2

9
1
3

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 47304 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=6003
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 47240 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1510
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 94612 KB Output is correct
2 Correct 566 ms 94464 KB Output is correct
3 Correct 966 ms 94408 KB Output is correct
4 Correct 745 ms 94352 KB Output is correct
5 Correct 613 ms 94352 KB Output is correct
6 Correct 512 ms 94596 KB Output is correct
7 Correct 546 ms 94512 KB Output is correct
8 Correct 60 ms 94368 KB Output is correct
9 Correct 62 ms 94432 KB Output is correct
10 Correct 58 ms 94516 KB Output is correct
11 Correct 593 ms 94436 KB Output is correct
12 Correct 545 ms 94644 KB Output is correct
13 Correct 582 ms 94768 KB Output is correct
14 Correct 509 ms 94456 KB Output is correct
15 Correct 121 ms 94464 KB Output is correct
16 Correct 128 ms 94616 KB Output is correct
17 Correct 171 ms 94504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 94344 KB Output is correct
2 Correct 742 ms 94376 KB Output is correct
3 Correct 687 ms 94432 KB Output is correct
4 Correct 61 ms 94348 KB Output is correct
5 Correct 57 ms 94356 KB Output is correct
6 Correct 57 ms 94396 KB Output is correct
7 Correct 645 ms 94460 KB Output is correct
8 Correct 976 ms 94368 KB Output is correct
9 Correct 759 ms 94508 KB Output is correct
10 Correct 657 ms 94352 KB Output is correct
11 Correct 66 ms 94412 KB Output is correct
12 Correct 62 ms 94412 KB Output is correct
13 Correct 59 ms 94328 KB Output is correct
14 Correct 68 ms 94388 KB Output is correct
15 Correct 59 ms 94404 KB Output is correct
16 Correct 545 ms 94356 KB Output is correct
17 Correct 563 ms 94444 KB Output is correct
18 Correct 555 ms 94352 KB Output is correct
19 Correct 551 ms 94372 KB Output is correct
20 Correct 576 ms 94408 KB Output is correct

Subtask #5
26.3244 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 598 ms 94536 KB Partially correct
2 Partially correct 507 ms 94620 KB Partially correct
3 Correct 931 ms 94468 KB Output is correct
4 Partially correct 706 ms 94344 KB Partially correct
5 Partially correct 620 ms 94368 KB Partially correct
6 Partially correct 494 ms 94564 KB Partially correct
7 Partially correct 489 ms 94480 KB Partially correct
8 Partially correct 57 ms 94404 KB Partially correct
9 Partially correct 60 ms 94396 KB Partially correct
10 Partially correct 60 ms 94340 KB Partially correct
11 Partially correct 499 ms 94552 KB Partially correct
12 Partially correct 609 ms 94488 KB Partially correct
13 Correct 925 ms 94448 KB Output is correct
14 Partially correct 724 ms 94316 KB Partially correct
15 Partially correct 666 ms 94368 KB Partially correct
16 Partially correct 532 ms 94472 KB Partially correct
17 Partially correct 644 ms 94376 KB Partially correct
18 Partially correct 519 ms 94564 KB Partially correct
19 Partially correct 566 ms 94600 KB Partially correct
20 Partially correct 520 ms 94500 KB Partially correct
21 Partially correct 127 ms 94480 KB Partially correct
22 Partially correct 141 ms 94472 KB Partially correct
23 Partially correct 163 ms 94480 KB Partially correct
24 Partially correct 69 ms 94388 KB Partially correct
25 Partially correct 61 ms 94480 KB Partially correct
26 Partially correct 59 ms 94472 KB Partially correct
27 Partially correct 59 ms 94380 KB Partially correct
28 Partially correct 58 ms 94716 KB Partially correct
29 Partially correct 585 ms 94352 KB Partially correct
30 Partially correct 557 ms 94352 KB Partially correct
31 Partially correct 588 ms 94416 KB Partially correct
32 Partially correct 604 ms 94372 KB Partially correct
33 Partially correct 620 ms 94344 KB Partially correct
34 Partially correct 394 ms 94600 KB Partially correct
35 Partially correct 498 ms 94632 KB Partially correct
36 Partially correct 536 ms 94552 KB Partially correct
37 Partially correct 568 ms 94624 KB Partially correct
38 Partially correct 540 ms 94480 KB Partially correct
39 Partially correct 548 ms 94688 KB Partially correct
40 Partially correct 496 ms 94696 KB Partially correct
41 Partially correct 519 ms 94572 KB Partially correct
42 Partially correct 115 ms 94576 KB Partially correct
43 Partially correct 171 ms 94480 KB Partially correct
44 Partially correct 206 ms 94568 KB Partially correct
45 Partially correct 227 ms 94480 KB Partially correct
46 Partially correct 383 ms 94488 KB Partially correct
47 Partially correct 384 ms 94540 KB Partially correct
48 Partially correct 124 ms 94596 KB Partially correct
49 Partially correct 123 ms 94800 KB Partially correct