oj.uz

Submission #1073098

# Submission time Handle Problem Language Result Execution time Memory
1073098 2024-08-24T09:30:23 Z Ignut Stations (IOI20_stations) C++17
10 / 100
 665 ms 944 KB 
// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1111;

vector<int> tree[N];

vector<int> dist;

void dfs(int v, int par, int d) {
    dist[v] = d;
    for (int to : tree[v])
        if (to != par)
            dfs(to, v, d + 1);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    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]);
    }

    vector<int> lbl(n);
    
    dist.resize(n);

    for (int i = 0; i < n; i ++) {
        dfs(i, -1, 0);
        vector<pair<int, int>> vec;
        for (int j = 0; j < n; j ++) vec.push_back({dist[j], j});
        sort(vec.begin(), vec.end());

        int maxDist = 0;
        for (int j = 0; j < n; j ++) maxDist = max(maxDist, dist[j]);

        lbl[i] = 0;
        for (int j = 0; j < n; j ++) lbl[i] = lbl[i] * 10 + vec[j].second + 1;

        lbl[i] = lbl[i] * 10 + maxDist;
    }

    // for (int val : lbl) cerr << val << ' ';
    // cerr << '\n';

    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 val : c) if (val == t) return t;

    // int tval;
    int tval = to_string(t)[0];
    while (t >= 10) t /= 10;
    // if (t != tval)
    //     return -10000;
    if (t == 0 || tval == 0)
        return -10000;
    tval = t;

    int bestPos = INF, ret = -1;
    int maxDist = INF;
    for (int v : c) {
        string str = to_string(v);
        int mxd = str.back() - '0';
        for (int i = 0; i + 1 < str.size(); i ++) {
            if ((str[i] - '0') == tval) {
                if (i < bestPos) {
                    bestPos = i;
                    ret = v;
                    maxDist = mxd;
                }
                else if (i == bestPos && mxd < maxDist) {
                    bestPos = i;
                    ret = v;
                    maxDist = mxd;
                }
            }
        }
    }
    return ret;
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 0; i + 1 < str.size(); i ++) {
      |                         ~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 944 KB Output is correct
2 Correct 488 ms 684 KB Output is correct
3 Correct 414 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 0 ms 776 KB Output is correct
7 Correct 422 ms 796 KB Output is correct
8 Correct 665 ms 684 KB Output is correct
9 Correct 459 ms 684 KB Output is correct
10 Correct 413 ms 684 KB Output is correct
11 Correct 3 ms 764 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 776 KB Output is correct
15 Correct 0 ms 776 KB Output is correct
16 Correct 342 ms 684 KB Output is correct
17 Correct 374 ms 684 KB Output is correct
18 Correct 368 ms 684 KB Output is correct
19 Correct 314 ms 684 KB Output is correct
20 Correct 356 ms 684 KB Output is correct

Subtask #5
0 / 61.0

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