oj.uz

Submission #306119

# Submission time Handle Problem Language Result Execution time Memory
306119 2020-09-24T14:35:58 Z SorahISA Stations (IOI20_stations) C++17
16 / 100
 897 ms 1272 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;

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

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);
    
    for (int i = 0; i < n-1; ++i) {
        adj[u[i]].eb(v[i]), adj[v[i]].eb(u[i]);
    }
    
    int maxDeg = 0;
    for (int i = 0; i < n; ++i) {
        if (adj[i].size() > adj[maxDeg].size()) maxDeg = i;
    }
    
    lab[maxDeg] = 0;
    int sz = adj[maxDeg].size();
    for (int i = 0; i < sz; ++i) {
        lab[adj[maxDeg][i]] = i * 1000 + 1;
        dfs(adj[maxDeg][i], maxDeg);
    }
    
	return lab;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s == 0) return t / 1000 * 1000 + 1;
    return s > t or s / 1000 != t / 1000 ? c.front() : c.back();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1005
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=3, label=1001
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 1272 KB Output is correct
2 Correct 484 ms 1008 KB Output is correct
3 Correct 897 ms 876 KB Output is correct
4 Correct 652 ms 880 KB Output is correct
5 Correct 596 ms 1024 KB Output is correct
6 Correct 441 ms 776 KB Output is correct
7 Correct 470 ms 800 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 2 ms 880 KB Output is correct
11 Correct 579 ms 876 KB Output is correct
12 Correct 499 ms 1140 KB Output is correct
13 Correct 484 ms 1008 KB Output is correct
14 Correct 456 ms 768 KB Output is correct
15 Correct 62 ms 872 KB Output is correct
16 Correct 69 ms 848 KB Output is correct
17 Correct 113 ms 804 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 876 KB Output is correct
2 Correct 693 ms 876 KB Output is correct
3 Correct 592 ms 880 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 2 ms 832 KB Output is correct
7 Correct 601 ms 872 KB Output is correct
8 Correct 844 ms 768 KB Output is correct
9 Correct 660 ms 768 KB Output is correct
10 Correct 584 ms 768 KB Output is correct
11 Incorrect 1 ms 384 KB Invalid labels (duplicates values). scenario=5, label=2
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 544 ms 1000 KB Partially correct
2 Partially correct 467 ms 1000 KB Partially correct
3 Correct 880 ms 768 KB Output is correct
4 Partially correct 741 ms 876 KB Partially correct
5 Partially correct 680 ms 876 KB Partially correct
6 Partially correct 539 ms 992 KB Partially correct
7 Partially correct 449 ms 768 KB Partially correct
8 Partially correct 2 ms 876 KB Partially correct
9 Partially correct 5 ms 1016 KB Partially correct
10 Partially correct 2 ms 768 KB Partially correct
11 Incorrect 5 ms 388 KB Invalid labels (duplicates values). scenario=0, label=3
12 Halted 0 ms 0 KB -