oj.uz

Submission #483324

# Submission time Handle Problem Language Result Execution time Memory
483324 2021-10-28T17:36:04 Z lukaszgniecki Stations (IOI20_stations) C++17
0 / 100
 918 ms 412 KB 
#include "stations.h"
#include <bits/stdc++.h>

#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vvvvll vector<vvvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)

using namespace std;

int find_next_station(int s, int t, vi neib) {
    if (neib.size() == 1)
        return neib[0];

    if (s < neib[0]) {
        int prev = s;
        for (int x : neib) {
            if (t > prev && t <= x) {
                return x;
            }
            prev = x;
        }
        return neib.back();
    }
    else {
        int prev = s;
        for (int i = neib.size() - 1; i >= 0; i--) {
            int x = neib[i];
            if (t < prev && t >= x) {
                return x;
            }
            prev = x;
        }
        return neib[0];
    }
}

int dfs_label(vvi & tr, int x, int p, int lvl, vi & lab) {
    if (lvl & 1) {
        lab[x] = lab[p];
        for (int y : tr[x]) {
            if (y != p) {
                lab[x] = dfs_label(tr, y, x, lvl + 1, lab);
            }
        }
        lab[x]++;
        return lab[x];
    }
    else {
        lab[x] = lab[p] + 1; // keep the root in mind
        int mx = lab[x];
        for (int y : tr[x]) {
            if (y != p) {
                mx = dfs_label(tr, y, x, lvl + 1, lab);
            }
        }
        return mx;
    }
}

vi label(int n, int k, vi u, vi v) {
    vvi tr(n);
    rep(i, 0, n - 1) {
        tr[u[i]].push_back(v[i]);
        tr[v[i]].push_back(u[i]);
    }
    vi lab(n, -1);
    dfs_label(tr, 0, 0, 0, lab);
    return lab;
}

/*
int main() {
    vi lab = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
    rep(i, 0, 5) {
        cout << lab[i] << " ";
    }
    cout << endl;
    cout << 0 << " " << 4 << " " << find_next_station(0, 4, {4}) << '\n';
    cout << 3 << " " << 2 << " " << find_next_station(3, 2, {4})<< '\n';
    cout << 3 << " " << 0 << " " << find_next_station(3, 0, {4})<< '\n';
    cout << 4 << " " << 0 << " " << find_next_station(4, 0, {0, 1, 3})<< '\n';
    cout << 4 << " " << 2 << " " << find_next_station(4, 2, {0, 1, 3})<< '\n';
    cout << 4 << " " << 3 << " " << find_next_station(4, 3, {0, 1, 3})<< '\n';

    lab = label(2, 1, {0}, {1});
}*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 412 KB Invalid labels (duplicates values). scenario=0, label=1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 268 KB Invalid labels (duplicates values). scenario=0, label=1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 408 KB Invalid labels (duplicates values). scenario=1, label=11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 400 KB Output is correct
2 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=1, label=1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 412 KB Invalid labels (duplicates values). scenario=1, label=91
2 Halted 0 ms 0 KB -