oj.uz

Submission #306149

# Submission time Handle Problem Language Result Execution time Memory
306149 2020-09-24T16:45:15 Z SorahISA Stations (IOI20_stations) C++17
10 / 100
 888 ms 1048 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

const int maxn = 1000 + 5;

vector<int> adj[maxn], lab, sz;
int tok = 0;

void dfs(int now, int lst) {
    lab[now] = tok++, sz[now] = 1;
    for (auto x : adj[now]) {
        if (x != lst) dfs(x, now), sz[now] += sz[x];
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i = 0; i < maxn; ++i) adj[i].clear();
    lab.resize(n), sz.resize(n);
    tok = 0;
    
    for (int i = 0; i < n-1; ++i) {
        adj[u[i]].eb(v[i]), adj[v[i]].eb(u[i]);
    }
    dfs(0, -1);
    
    for (int i = 0; i < n; ++i) lab[i] = lab[i] * 1000 + sz[i];
    
    // cout << "lab : ";
    // for (int i = 0; i < n; ++i) cout << lab[i] << " \n"[i == n-1];
    
    return lab;
}

int find_next_station(int s, int t, vector<int> c) {
    sort(ALL(c), [](auto a, auto b) {return a/1000 < b/1000;});
    // cout << "c : "; for (auto x : c) cout << x << " "; cout << "\n";
    if (s/1000 > t/1000 or s/1000 + s%1000 <= t/1000) return c[0];
    for (int i = 1; i < c.size(); ++i) {
        if (c[i]/1000 > t/1000) return c[i - 1];
    }
    return c.back();
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 884 KB Output is correct
2 Correct 704 ms 1048 KB Output is correct
3 Correct 602 ms 768 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 880 KB Output is correct
7 Correct 586 ms 872 KB Output is correct
8 Correct 888 ms 1008 KB Output is correct
9 Correct 668 ms 768 KB Output is correct
10 Correct 606 ms 872 KB Output is correct
11 Correct 5 ms 876 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 558 ms 768 KB Output is correct
17 Correct 533 ms 880 KB Output is correct
18 Correct 546 ms 768 KB Output is correct
19 Correct 531 ms 1008 KB Output is correct
20 Correct 531 ms 908 KB Output is correct

Subtask #5
0 / 61.0

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