oj.uz

Submission #305708

# Submission time Handle Problem Language Result Execution time Memory
305708 2020-09-23T20:38:32 Z peti1234 Stations (IOI20_stations) C++17
100 / 100
 1031 ms 1152 KB 
#include <bits/stdc++.h>
#include "stations.h"
using namespace std;
const int c=1002;
vector<int> sz[c], sol;
bool v[c];
int cnt;
void dfs(int a, bool b) {
    v[a]=1;
    if (!b) sol[a]=cnt++;
    for (int i=0; i<sz[a].size(); i++) {
        int x=sz[a][i];
        if (!v[x]) dfs(x, !b);
    }
    if (b) sol[a]=cnt++;
}
vector<int> label(int n, int k, vector<int> x, vector<int> y) {
    for (int i=0; i<n; i++) sz[i].clear(), v[i]=0, cnt=0, sol.clear();
    sol.resize(n);
    for (int i=0; i<n-1; i++) sz[x[i]].push_back(y[i]), sz[y[i]].push_back(x[i]);
    dfs(0, 0);
    //for(int i=0; i<n; i++) cout << sol[i] << " ";
    return sol;
}
int find_next_station(int s, int t, vector<int> sz) {
    int x=sz[0], y=sz.back(), si=sz.size();
    if (s<x) {
        if (t<s || t>y) return y;
        for (int i=0; i<si; i++) if (sz[i]>=t) return sz[i];
    }
    if (t>s || t<x) return x;
    for (int i=si-1; i>0; i--) if (sz[i]<=t) return sz[i];
}

Compilation message

stations.cpp: In function 'void dfs(int, bool)':
stations.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=0; i<sz[a].size(); i++) {
      |                   ~^~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 768 KB Output is correct
2 Correct 446 ms 768 KB Output is correct
3 Correct 850 ms 768 KB Output is correct
4 Correct 669 ms 768 KB Output is correct
5 Correct 767 ms 768 KB Output is correct
6 Correct 485 ms 768 KB Output is correct
7 Correct 580 ms 808 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 1 ms 884 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 808 KB Output is correct
2 Correct 548 ms 768 KB Output is correct
3 Correct 907 ms 1040 KB Output is correct
4 Correct 659 ms 884 KB Output is correct
5 Correct 617 ms 1024 KB Output is correct
6 Correct 527 ms 832 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 768 KB Output is correct
2 Correct 466 ms 768 KB Output is correct
3 Correct 906 ms 880 KB Output is correct
4 Correct 729 ms 888 KB Output is correct
5 Correct 597 ms 1152 KB Output is correct
6 Correct 529 ms 784 KB Output is correct
7 Correct 541 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 880 KB Output is correct
10 Correct 2 ms 880 KB Output is correct
11 Correct 578 ms 880 KB Output is correct
12 Correct 524 ms 892 KB Output is correct
13 Correct 471 ms 772 KB Output is correct
14 Correct 496 ms 824 KB Output is correct
15 Correct 68 ms 908 KB Output is correct
16 Correct 63 ms 1092 KB Output is correct
17 Correct 108 ms 812 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 768 KB Output is correct
2 Correct 751 ms 888 KB Output is correct
3 Correct 599 ms 768 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 1 ms 872 KB Output is correct
7 Correct 626 ms 868 KB Output is correct
8 Correct 1031 ms 876 KB Output is correct
9 Correct 742 ms 876 KB Output is correct
10 Correct 583 ms 1008 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 6 ms 884 KB Output is correct
13 Correct 4 ms 768 KB Output is correct
14 Correct 4 ms 1004 KB Output is correct
15 Correct 2 ms 768 KB Output is correct
16 Correct 527 ms 880 KB Output is correct
17 Correct 540 ms 1044 KB Output is correct
18 Correct 513 ms 876 KB Output is correct
19 Correct 505 ms 880 KB Output is correct
20 Correct 512 ms 768 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 780 KB Output is correct
2 Correct 467 ms 904 KB Output is correct
3 Correct 861 ms 768 KB Output is correct
4 Correct 646 ms 876 KB Output is correct
5 Correct 559 ms 768 KB Output is correct
6 Correct 457 ms 776 KB Output is correct
7 Correct 450 ms 936 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 4 ms 1056 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 455 ms 768 KB Output is correct
12 Correct 534 ms 848 KB Output is correct
13 Correct 896 ms 768 KB Output is correct
14 Correct 689 ms 880 KB Output is correct
15 Correct 620 ms 768 KB Output is correct
16 Correct 461 ms 820 KB Output is correct
17 Correct 605 ms 896 KB Output is correct
18 Correct 455 ms 920 KB Output is correct
19 Correct 489 ms 888 KB Output is correct
20 Correct 510 ms 828 KB Output is correct
21 Correct 61 ms 864 KB Output is correct
22 Correct 88 ms 768 KB Output is correct
23 Correct 108 ms 768 KB Output is correct
24 Correct 6 ms 876 KB Output is correct
25 Correct 5 ms 768 KB Output is correct
26 Correct 5 ms 876 KB Output is correct
27 Correct 4 ms 880 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 500 ms 876 KB Output is correct
30 Correct 524 ms 880 KB Output is correct
31 Correct 534 ms 768 KB Output is correct
32 Correct 521 ms 768 KB Output is correct
33 Correct 521 ms 880 KB Output is correct
34 Correct 317 ms 784 KB Output is correct
35 Correct 447 ms 1024 KB Output is correct
36 Correct 454 ms 992 KB Output is correct
37 Correct 457 ms 780 KB Output is correct
38 Correct 504 ms 904 KB Output is correct
39 Correct 488 ms 788 KB Output is correct
40 Correct 493 ms 784 KB Output is correct
41 Correct 467 ms 792 KB Output is correct
42 Correct 67 ms 832 KB Output is correct
43 Correct 137 ms 768 KB Output is correct
44 Correct 159 ms 768 KB Output is correct
45 Correct 207 ms 792 KB Output is correct
46 Correct 329 ms 896 KB Output is correct
47 Correct 392 ms 800 KB Output is correct
48 Correct 75 ms 768 KB Output is correct
49 Correct 76 ms 1024 KB Output is correct