oj.uz

Submission #985512

# Submission time Handle Problem Language Result Execution time Memory
985512 2024-05-18T02:28:47 Z Maaxle Stations (IOI20_stations) C++17
100 / 100
 607 ms 1464 KB 
#include "stations.h"
#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>

using namespace std;

static void dfs(int i, int p, int d, int& timer, vector<vector<int>>& adj, vector<int>& l) {    
    if (!(d & 1))
        l[i] = timer++;

    for (int& k : adj[i]) {
        if (k != p)
            dfs(k, i, d+1, timer, adj, l);
    }

    if (d & 1)  
        l[i] += timer++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    vector<vector<int>> adj (n);
    vector<int> l (n);

    range(i, 0, n-1) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    int timer = 0;
    dfs(0, 0, 0, timer, adj, l);
    return l;
}
		

int find_next_station(int s, int t, vector<int> c) {
    // CASE 1 -> s has an 'in' value
    // every node in c has value 'out'
    // the parent of them all is the right-most value
    // s is the left-most value
    if (s < c[0]) {

        // CASE 1.1 -> t is not a decendant of s
        // and t is before s
        if ((t < s || c.size() == 1 || t > c[c.size() - 2]) && s != 0) 
            return c.back();
            
        // CASE 1.2 -> t may or not be decendant of s
        // ancestor of t is the first in c that is >= t
        return *lower_bound(all(c), t);
    }

    // CASE 2 -> s has an 'out' value
    // every node in c has value 'in'
    // the parent of them all is the left-most value
    // s is the right-most value
    
    // CASE 2.1 -> t is not a decendant of s
    //  and t is after s
    if (t > s || c.size() == 1 || t < c[1]) 
        return c[0];
    
    // CASE 2.2 -> t may or not be a decendant of s
    // ancestor of t is the first in c that is <= t (backwards)
    return *(--upper_bound(all(c), t));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 932 KB Output is correct
2 Correct 288 ms 936 KB Output is correct
3 Correct 597 ms 684 KB Output is correct
4 Correct 422 ms 684 KB Output is correct
5 Correct 377 ms 720 KB Output is correct
6 Correct 296 ms 920 KB Output is correct
7 Correct 299 ms 684 KB Output is correct
8 Correct 1 ms 764 KB Output is correct
9 Correct 2 ms 1272 KB Output is correct
10 Correct 0 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 872 KB Output is correct
2 Correct 362 ms 792 KB Output is correct
3 Correct 604 ms 684 KB Output is correct
4 Correct 430 ms 684 KB Output is correct
5 Correct 384 ms 684 KB Output is correct
6 Correct 282 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 936 KB Output is correct
2 Correct 320 ms 940 KB Output is correct
3 Correct 569 ms 688 KB Output is correct
4 Correct 423 ms 684 KB Output is correct
5 Correct 401 ms 684 KB Output is correct
6 Correct 276 ms 912 KB Output is correct
7 Correct 280 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 383 ms 684 KB Output is correct
12 Correct 291 ms 940 KB Output is correct
13 Correct 316 ms 1264 KB Output is correct
14 Correct 310 ms 688 KB Output is correct
15 Correct 33 ms 764 KB Output is correct
16 Correct 43 ms 908 KB Output is correct
17 Correct 60 ms 852 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 936 KB Output is correct
2 Correct 403 ms 684 KB Output is correct
3 Correct 365 ms 684 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 381 ms 684 KB Output is correct
8 Correct 607 ms 856 KB Output is correct
9 Correct 426 ms 684 KB Output is correct
10 Correct 418 ms 684 KB Output is correct
11 Correct 4 ms 772 KB Output is correct
12 Correct 3 ms 768 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 1 ms 836 KB Output is correct
16 Correct 330 ms 684 KB Output is correct
17 Correct 328 ms 936 KB Output is correct
18 Correct 344 ms 684 KB Output is correct
19 Correct 331 ms 684 KB Output is correct
20 Correct 307 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 932 KB Output is correct
2 Correct 263 ms 928 KB Output is correct
3 Correct 564 ms 684 KB Output is correct
4 Correct 438 ms 684 KB Output is correct
5 Correct 362 ms 684 KB Output is correct
6 Correct 323 ms 936 KB Output is correct
7 Correct 266 ms 684 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 3 ms 764 KB Output is correct
10 Correct 0 ms 1012 KB Output is correct
11 Correct 301 ms 852 KB Output is correct
12 Correct 355 ms 820 KB Output is correct
13 Correct 559 ms 684 KB Output is correct
14 Correct 401 ms 684 KB Output is correct
15 Correct 407 ms 688 KB Output is correct
16 Correct 278 ms 684 KB Output is correct
17 Correct 398 ms 684 KB Output is correct
18 Correct 293 ms 1168 KB Output is correct
19 Correct 303 ms 1268 KB Output is correct
20 Correct 287 ms 684 KB Output is correct
21 Correct 30 ms 764 KB Output is correct
22 Correct 44 ms 1160 KB Output is correct
23 Correct 63 ms 932 KB Output is correct
24 Correct 4 ms 768 KB Output is correct
25 Correct 3 ms 768 KB Output is correct
26 Correct 3 ms 768 KB Output is correct
27 Correct 2 ms 768 KB Output is correct
28 Correct 1 ms 772 KB Output is correct
29 Correct 362 ms 684 KB Output is correct
30 Correct 331 ms 684 KB Output is correct
31 Correct 287 ms 684 KB Output is correct
32 Correct 387 ms 684 KB Output is correct
33 Correct 348 ms 684 KB Output is correct
34 Correct 220 ms 904 KB Output is correct
35 Correct 293 ms 976 KB Output is correct
36 Correct 272 ms 1016 KB Output is correct
37 Correct 284 ms 940 KB Output is correct
38 Correct 293 ms 1120 KB Output is correct
39 Correct 319 ms 964 KB Output is correct
40 Correct 275 ms 1136 KB Output is correct
41 Correct 335 ms 968 KB Output is correct
42 Correct 37 ms 884 KB Output is correct
43 Correct 66 ms 856 KB Output is correct
44 Correct 82 ms 912 KB Output is correct
45 Correct 91 ms 856 KB Output is correct
46 Correct 234 ms 856 KB Output is correct
47 Correct 185 ms 900 KB Output is correct
48 Correct 41 ms 1116 KB Output is correct
49 Correct 33 ms 1464 KB Output is correct