oj.uz

Submission #683739

# Submission time Handle Problem Language Result Execution time Memory
683739 2023-01-19T08:50:54 Z sharaelong Stations (IOI20_stations) C++17
100 / 100
 912 ms 768 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int MAX_N = 1000;
vector<int> adj[MAX_N];
int depth[MAX_N];
int tour[MAX_N];
int tour_cnt = 0;

void dfs(int here, int parent = -1) {
    if (~depth[here] & 1) tour[here] = tour_cnt;
    for (int there: adj[here]) {
        if (there != parent) {
            depth[there] = depth[here] + 1;
            if (~depth[here] & 1) tour_cnt++;
            dfs(there, here);
        }
    }
    if (depth[here] & 1) {
        tour[here] = tour_cnt;
    } else {
        tour_cnt++;
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    for (int i=0; i<n; ++i) adj[i].clear();
    tour_cnt = 0;
    memset(depth, 0, sizeof depth);
    
    for (int i=0; i<n-1; ++i) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs(0);
    assert(tour_cnt == n);

	vector<int> labels(n);
	for (int i=0; i<n; i++) labels[i] = tour[i];
    // cout << endl;
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
    if (c.size() == 1) return c[0];
    // s is start
    if (s < c[0]) {
        if (s < t && t <= c[c.size()-2]) {
            for (int i=0; i+1<c.size(); ++i) {
                if (t <= c[i]) return c[i];
            }
        } else {
            return c.back();
        }
    } else {
        if (s > t && t >= c[1]) {
            for (int i=1; i+1<c.size(); ++i) {
                if (c[i] <= t && t < c[i+1]) return c[i];
            }
            return c.back();
        } else {
            return c[0];
        }
    }
    assert(false);
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 544 KB Output is correct
2 Correct 464 ms 544 KB Output is correct
3 Correct 912 ms 416 KB Output is correct
4 Correct 563 ms 548 KB Output is correct
5 Correct 555 ms 416 KB Output is correct
6 Correct 407 ms 632 KB Output is correct
7 Correct 439 ms 536 KB Output is correct
8 Correct 3 ms 488 KB Output is correct
9 Correct 4 ms 492 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 537 ms 536 KB Output is correct
2 Correct 565 ms 544 KB Output is correct
3 Correct 753 ms 516 KB Output is correct
4 Correct 663 ms 532 KB Output is correct
5 Correct 608 ms 416 KB Output is correct
6 Correct 462 ms 548 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 656 KB Output is correct
2 Correct 434 ms 528 KB Output is correct
3 Correct 866 ms 416 KB Output is correct
4 Correct 656 ms 420 KB Output is correct
5 Correct 655 ms 416 KB Output is correct
6 Correct 422 ms 544 KB Output is correct
7 Correct 435 ms 544 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 618 ms 536 KB Output is correct
12 Correct 392 ms 652 KB Output is correct
13 Correct 427 ms 668 KB Output is correct
14 Correct 426 ms 536 KB Output is correct
15 Correct 56 ms 552 KB Output is correct
16 Correct 54 ms 572 KB Output is correct
17 Correct 93 ms 760 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 420 KB Output is correct
2 Correct 570 ms 532 KB Output is correct
3 Correct 608 ms 548 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 604 ms 416 KB Output is correct
8 Correct 845 ms 528 KB Output is correct
9 Correct 607 ms 544 KB Output is correct
10 Correct 585 ms 564 KB Output is correct
11 Correct 6 ms 492 KB Output is correct
12 Correct 3 ms 492 KB Output is correct
13 Correct 4 ms 500 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 2 ms 500 KB Output is correct
16 Correct 503 ms 420 KB Output is correct
17 Correct 508 ms 420 KB Output is correct
18 Correct 469 ms 456 KB Output is correct
19 Correct 506 ms 540 KB Output is correct
20 Correct 434 ms 548 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 536 KB Output is correct
2 Correct 424 ms 548 KB Output is correct
3 Correct 774 ms 416 KB Output is correct
4 Correct 599 ms 612 KB Output is correct
5 Correct 583 ms 420 KB Output is correct
6 Correct 416 ms 548 KB Output is correct
7 Correct 429 ms 532 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 5 ms 500 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 475 ms 664 KB Output is correct
12 Correct 523 ms 572 KB Output is correct
13 Correct 777 ms 420 KB Output is correct
14 Correct 624 ms 528 KB Output is correct
15 Correct 551 ms 544 KB Output is correct
16 Correct 421 ms 548 KB Output is correct
17 Correct 592 ms 532 KB Output is correct
18 Correct 471 ms 640 KB Output is correct
19 Correct 375 ms 532 KB Output is correct
20 Correct 445 ms 552 KB Output is correct
21 Correct 40 ms 544 KB Output is correct
22 Correct 61 ms 596 KB Output is correct
23 Correct 87 ms 544 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 7 ms 524 KB Output is correct
26 Correct 5 ms 492 KB Output is correct
27 Correct 4 ms 500 KB Output is correct
28 Correct 1 ms 620 KB Output is correct
29 Correct 400 ms 444 KB Output is correct
30 Correct 424 ms 536 KB Output is correct
31 Correct 356 ms 516 KB Output is correct
32 Correct 503 ms 528 KB Output is correct
33 Correct 526 ms 548 KB Output is correct
34 Correct 322 ms 532 KB Output is correct
35 Correct 415 ms 544 KB Output is correct
36 Correct 381 ms 532 KB Output is correct
37 Correct 450 ms 712 KB Output is correct
38 Correct 411 ms 636 KB Output is correct
39 Correct 457 ms 656 KB Output is correct
40 Correct 453 ms 752 KB Output is correct
41 Correct 470 ms 768 KB Output is correct
42 Correct 63 ms 544 KB Output is correct
43 Correct 109 ms 672 KB Output is correct
44 Correct 116 ms 620 KB Output is correct
45 Correct 147 ms 616 KB Output is correct
46 Correct 292 ms 532 KB Output is correct
47 Correct 297 ms 536 KB Output is correct
48 Correct 54 ms 700 KB Output is correct
49 Correct 42 ms 752 KB Output is correct