oj.uz

Submission #1073118

# Submission time Handle Problem Language Result Execution time Memory
1073118 2024-08-24T09:39:42 Z Ignut Stations (IOI20_stations) C++17
16 / 100
 3000 ms 5676 KB 
// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 123;
const int C = 1000;

vector<int> tree[N];

vector<int> euler;

int root;

void dfs(int v, int par) {
    euler.push_back(v);
    for (int to : tree[v]) {
        if (to != par) {
            dfs(to, v);
            if (v == root)
                euler.push_back(v);
        }
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    euler.clear();
    for (int i = 0; i < n; i ++) {
        tree[i].clear();
    }

    for (int i = 0; i < n - 1; i ++) {
        tree[u[i]].push_back(v[i]);
        tree[v[i]].push_back(u[i]);
    }

    root = 0;
    for (int i = 0; i < n; i ++)
        if (tree[i].size() > 2)
            root = i;
    
    dfs(root, -1);

    vector<int> lbl(n);
    lbl[root] = 0;

    int val = 0;
    for (int v : euler) {
        if (v == root) {
            val = ((val / C) + 1) * C;
            val ++;
            continue;
        }
        lbl[v] = val;
        val ++;
    }

    return lbl;
}

const int INF = 1e9 + 123;

int find_next_station(int s, int t, vector<int> c) {
    if (c.size() == 1)
        return c[0];
    for (int v : c)
        if (v == t)
            return t;
    bool isRoot = true;
    for (int v : c) {
        if (v % C != 1)
            isRoot = false;
    }
    if (isRoot) {
        for (int v : c) {
            if (v / C == t / C)
                return v;
        }
        while (true);
        return c[0];
    }

    //

    if (c.size() != 2)
        while (true);
    
    int mn = min(c[0], c[1]);
    int mx = max(c[0], c[1]);

    if (mx / C == t / C) {
        // we are in the correct chain
        if (mx % C <= t % C)
            return mx;
        return mn;
    }

    // we are in the incorrect chain
    return mn;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 5548 KB Output is correct
2 Correct 363 ms 5548 KB Output is correct
3 Correct 660 ms 5292 KB Output is correct
4 Correct 502 ms 5296 KB Output is correct
5 Correct 430 ms 5292 KB Output is correct
6 Correct 296 ms 5552 KB Output is correct
7 Correct 325 ms 5292 KB Output is correct
8 Correct 2 ms 5380 KB Output is correct
9 Correct 4 ms 5384 KB Output is correct
10 Correct 3 ms 5384 KB Output is correct
11 Correct 432 ms 5292 KB Output is correct
12 Correct 357 ms 5672 KB Output is correct
13 Correct 338 ms 5676 KB Output is correct
14 Correct 326 ms 5292 KB Output is correct
15 Correct 27 ms 5380 KB Output is correct
16 Correct 41 ms 5296 KB Output is correct
17 Correct 69 ms 5384 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 5292 KB Output is correct
2 Correct 460 ms 5292 KB Output is correct
3 Correct 428 ms 5292 KB Output is correct
4 Correct 4 ms 5380 KB Output is correct
5 Correct 3 ms 5500 KB Output is correct
6 Correct 2 ms 5384 KB Output is correct
7 Correct 426 ms 5292 KB Output is correct
8 Correct 635 ms 5292 KB Output is correct
9 Correct 435 ms 5292 KB Output is correct
10 Correct 393 ms 5292 KB Output is correct
11 Execution timed out 3089 ms 5380 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 309 ms 5548 KB Partially correct
2 Partially correct 258 ms 5548 KB Partially correct
3 Partially correct 512 ms 5292 KB Partially correct
4 Partially correct 468 ms 5292 KB Partially correct
5 Partially correct 398 ms 5544 KB Partially correct
6 Partially correct 298 ms 5548 KB Partially correct
7 Partially correct 304 ms 5292 KB Partially correct
8 Partially correct 4 ms 5380 KB Partially correct
9 Partially correct 3 ms 5380 KB Partially correct
10 Partially correct 2 ms 5392 KB Partially correct
11 Execution timed out 3035 ms 5292 KB Time limit exceeded
12 Halted 0 ms 0 KB -