oj.uz

Submission #682022

# Submission time Handle Problem Language Result Execution time Memory
682022 2023-01-15T09:15:53 Z junkbot Stations (IOI20_stations) C++14
100 / 100
 988 ms 716 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

#define D(x...) fprintf(stderr, x)
#define D(x...)

const int MAX_N = 1005;
const int UNLABELLED = -1;
const int PENDING = -2;

struct Solve {
    int upto;
    vector<vector<int>> adjlist;
    vector<int> labels;

    Solve(int n, vector<int> u, vector<int> v) : upto(0), adjlist(n), labels(n) {
        for (auto i=0;i<n-1;i++) {
            adjlist[u[i]].push_back(v[i]);
            adjlist[v[i]].push_back(u[i]);
        }
        fill(labels.begin(), labels.end(), UNLABELLED);
    }

    // label everything in u's subtree.
    void go(int u, bool isPre) {
        if (labels[u] != UNLABELLED) return;
        labels[u] = PENDING;

        if (isPre) labels[u] = getNext();
        for (auto v: adjlist[u]) go(v, !isPre);
        if (!isPre) labels[u] = getNext();
    }

    int getNext() {
        int ret = upto;
        upto++;
        return ret;
    }
};

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    auto solver = Solve(n, u, v);
    solver.go(0, true);

    D("labels:");
    for (auto l: solver.labels) {
        D(" %d", l);
    }
    D("\n");

	return solver.labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    if (s < c.front()) {
        // preorder
        int left_exclusive = s;
        for (auto i=0;i<c.size()-1;i++) {
            auto l = c[i];
            if (left_exclusive < t && t <= l) return l;
            left_exclusive = l;
        }
        return c.back();
    } else {
        // postorder
        int right_exclusive = s;
        for (auto i=c.size()-1;i>0;i--) {
            auto l = c[i];
            if (l <= t && t < right_exclusive) return l;
            right_exclusive = l;
        }
        return c.front();
    }
}

Compilation message

stations.cpp:7: warning: "D" redefined
    7 | #define D(x...)
      | 
stations.cpp:6: note: this is the location of the previous definition
    6 | #define D(x...) fprintf(stderr, x)
      | 
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:48:15: warning: unused variable 'l' [-Wunused-variable]
   48 |     for (auto l: solver.labels) {
      |               ^
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:60:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (auto i=0;i<c.size()-1;i++) {
      |                       ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 648 KB Output is correct
2 Correct 387 ms 576 KB Output is correct
3 Correct 988 ms 560 KB Output is correct
4 Correct 573 ms 504 KB Output is correct
5 Correct 703 ms 504 KB Output is correct
6 Correct 522 ms 608 KB Output is correct
7 Correct 481 ms 544 KB Output is correct
8 Correct 2 ms 496 KB Output is correct
9 Correct 3 ms 496 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 512 KB Output is correct
2 Correct 484 ms 544 KB Output is correct
3 Correct 927 ms 552 KB Output is correct
4 Correct 666 ms 572 KB Output is correct
5 Correct 594 ms 504 KB Output is correct
6 Correct 511 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 548 KB Output is correct
2 Correct 473 ms 616 KB Output is correct
3 Correct 940 ms 492 KB Output is correct
4 Correct 711 ms 484 KB Output is correct
5 Correct 656 ms 416 KB Output is correct
6 Correct 429 ms 508 KB Output is correct
7 Correct 441 ms 544 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 500 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 613 ms 416 KB Output is correct
12 Correct 453 ms 680 KB Output is correct
13 Correct 492 ms 548 KB Output is correct
14 Correct 374 ms 548 KB Output is correct
15 Correct 46 ms 472 KB Output is correct
16 Correct 60 ms 620 KB Output is correct
17 Correct 95 ms 544 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 420 KB Output is correct
2 Correct 610 ms 544 KB Output is correct
3 Correct 556 ms 420 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 0 ms 500 KB Output is correct
7 Correct 541 ms 504 KB Output is correct
8 Correct 779 ms 504 KB Output is correct
9 Correct 670 ms 504 KB Output is correct
10 Correct 588 ms 420 KB Output is correct
11 Correct 6 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 4 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 478 ms 508 KB Output is correct
17 Correct 497 ms 500 KB Output is correct
18 Correct 456 ms 500 KB Output is correct
19 Correct 484 ms 544 KB Output is correct
20 Correct 497 ms 508 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 544 KB Output is correct
2 Correct 452 ms 512 KB Output is correct
3 Correct 827 ms 416 KB Output is correct
4 Correct 546 ms 416 KB Output is correct
5 Correct 514 ms 416 KB Output is correct
6 Correct 373 ms 548 KB Output is correct
7 Correct 464 ms 508 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 464 ms 504 KB Output is correct
12 Correct 382 ms 500 KB Output is correct
13 Correct 787 ms 420 KB Output is correct
14 Correct 538 ms 416 KB Output is correct
15 Correct 533 ms 504 KB Output is correct
16 Correct 443 ms 548 KB Output is correct
17 Correct 562 ms 484 KB Output is correct
18 Correct 380 ms 624 KB Output is correct
19 Correct 478 ms 696 KB Output is correct
20 Correct 436 ms 548 KB Output is correct
21 Correct 48 ms 468 KB Output is correct
22 Correct 64 ms 600 KB Output is correct
23 Correct 98 ms 592 KB Output is correct
24 Correct 5 ms 504 KB Output is correct
25 Correct 4 ms 492 KB Output is correct
26 Correct 3 ms 500 KB Output is correct
27 Correct 2 ms 500 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 427 ms 420 KB Output is correct
30 Correct 525 ms 508 KB Output is correct
31 Correct 508 ms 416 KB Output is correct
32 Correct 498 ms 504 KB Output is correct
33 Correct 512 ms 508 KB Output is correct
34 Correct 302 ms 544 KB Output is correct
35 Correct 416 ms 548 KB Output is correct
36 Correct 458 ms 588 KB Output is correct
37 Correct 403 ms 584 KB Output is correct
38 Correct 418 ms 716 KB Output is correct
39 Correct 447 ms 668 KB Output is correct
40 Correct 468 ms 588 KB Output is correct
41 Correct 447 ms 640 KB Output is correct
42 Correct 56 ms 600 KB Output is correct
43 Correct 97 ms 500 KB Output is correct
44 Correct 140 ms 544 KB Output is correct
45 Correct 141 ms 544 KB Output is correct
46 Correct 278 ms 572 KB Output is correct
47 Correct 323 ms 544 KB Output is correct
48 Correct 52 ms 572 KB Output is correct
49 Correct 59 ms 668 KB Output is correct