oj.uz

Submission #1072996

# Submission time Handle Problem Language Result Execution time Memory
1072996 2024-08-24T08:09:29 Z Ignut Stations (IOI20_stations) C++17
8 / 100
 638 ms 936 KB 
// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1111;

vector<int> tree[N];

vector<int> order;

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

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    // order.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]);
    // }
    // int start = 0;
    // for (int i = 0; i < n; i ++)
    //     if (tree[i].size() == 1)
    //         start = i;
    // dfs(start, -1);

    vector<int> lbl(n);
    for (int i = 0; i < n; i ++) lbl[i] = i;

    return lbl;
}


bool isInSubtree(int rt, int v) {
    int l = rt, r = rt;
    while (v > r) {
        l = l * 2 + 1, r = r * 2 + 2;
    }
    return (l <= v && v <= r);
}

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

    int mx = 0;
    for (int val : c) mx = max(mx, val);
    if (isInSubtree(mx, t))
        return mx;

    for (int val : c) {
        if (val == mx - 1) {
            if (isInSubtree(val, t))
                return val;
        }
    }

    int mn = 1111;
    for (int val : c) mn = min(mn, val);
    return mn;

    if (isInSubtree(c.back(), t))
        return c.back();
    c.pop_back();
    if (isInSubtree(c.back(), t))
        return c.back();
    c.pop_back();
    return c[0];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 372 ms 936 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 684 KB Output is correct
2 Correct 332 ms 684 KB Output is correct
3 Correct 638 ms 684 KB Output is correct
4 Correct 440 ms 684 KB Output is correct
5 Correct 422 ms 684 KB Output is correct
6 Correct 300 ms 684 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 684 KB Output is correct
2 Correct 454 ms 684 KB Output is correct
3 Incorrect 443 ms 684 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 390 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -