oj.uz

Submission #732176

# Submission time Handle Problem Language Result Execution time Memory
732176 2023-04-28T14:57:07 Z PoonYaPat Stations (IOI20_stations) C++14
100 / 100
 942 ms 892 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1001],A;
int ans[1001],cnt;

void dfs(int x, int par, int level) {
    if (level%2==0) ans[x]=++cnt;
    for (auto s : adj[x]) {
        if (s!=par) dfs(s,x,level+1);
    }
    if (level%2==1) ans[x]=++cnt;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    cnt=0;
    A.clear();
    for (int i=0; i<n; ++i) adj[i].clear();

    for (int i=0; i<n-1; ++i) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    dfs(0,0,0);
    for (int i=0; i<n; ++i) A.push_back(ans[i]);
    return A;
}

int find_next_station(int s, int t, vector<int> c) {
    if (s==1) {
        int ans;
        for (int i=c.size()-1; i>=0; --i) if (t<=c[i]) ans=c[i];
        return ans;
    }

    if (s>c[0]) {
        if (c.size()==1) return c[0];
        if (t<c[1] || t>s) return c[0];

        int ans;
        for (int i=1; i<c.size(); ++i) if (t>=c[i]) ans=c[i];
        return ans;

    } else {
        if (c.size()==1) return c[0];
        if (t<s || t>c[c.size()-2]) return c.back();

        int ans;
        for (int i=c.size()-2; i>=0; --i) if (t<=c[i]) ans=c[i];
        return ans;
    }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:42:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i=1; i<c.size(); ++i) if (t>=c[i]) ans=c[i];
      |                       ~^~~~~~~~~
stations.cpp:49:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |         int ans;
      |             ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 668 KB Output is correct
2 Correct 451 ms 780 KB Output is correct
3 Correct 848 ms 420 KB Output is correct
4 Correct 577 ms 420 KB Output is correct
5 Correct 616 ms 420 KB Output is correct
6 Correct 408 ms 660 KB Output is correct
7 Correct 471 ms 532 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 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 528 KB Output is correct
2 Correct 506 ms 524 KB Output is correct
3 Correct 859 ms 512 KB Output is correct
4 Correct 656 ms 532 KB Output is correct
5 Correct 632 ms 416 KB Output is correct
6 Correct 422 ms 544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 724 KB Output is correct
2 Correct 460 ms 656 KB Output is correct
3 Correct 855 ms 420 KB Output is correct
4 Correct 649 ms 420 KB Output is correct
5 Correct 542 ms 528 KB Output is correct
6 Correct 472 ms 676 KB Output is correct
7 Correct 438 ms 532 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 500 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 575 ms 536 KB Output is correct
12 Correct 484 ms 892 KB Output is correct
13 Correct 437 ms 780 KB Output is correct
14 Correct 450 ms 548 KB Output is correct
15 Correct 52 ms 432 KB Output is correct
16 Correct 67 ms 544 KB Output is correct
17 Correct 127 ms 544 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 416 KB Output is correct
2 Correct 656 ms 416 KB Output is correct
3 Correct 527 ms 420 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 0 ms 500 KB Output is correct
7 Correct 620 ms 532 KB Output is correct
8 Correct 823 ms 516 KB Output is correct
9 Correct 645 ms 416 KB Output is correct
10 Correct 579 ms 416 KB Output is correct
11 Correct 6 ms 496 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 2 ms 500 KB Output is correct
14 Correct 4 ms 492 KB Output is correct
15 Correct 2 ms 500 KB Output is correct
16 Correct 492 ms 528 KB Output is correct
17 Correct 496 ms 420 KB Output is correct
18 Correct 475 ms 664 KB Output is correct
19 Correct 531 ms 416 KB Output is correct
20 Correct 459 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 636 KB Output is correct
2 Correct 448 ms 520 KB Output is correct
3 Correct 919 ms 516 KB Output is correct
4 Correct 619 ms 420 KB Output is correct
5 Correct 553 ms 420 KB Output is correct
6 Correct 381 ms 672 KB Output is correct
7 Correct 423 ms 532 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 426 ms 540 KB Output is correct
12 Correct 486 ms 580 KB Output is correct
13 Correct 942 ms 420 KB Output is correct
14 Correct 681 ms 528 KB Output is correct
15 Correct 707 ms 420 KB Output is correct
16 Correct 494 ms 548 KB Output is correct
17 Correct 568 ms 528 KB Output is correct
18 Correct 427 ms 660 KB Output is correct
19 Correct 426 ms 548 KB Output is correct
20 Correct 466 ms 532 KB Output is correct
21 Correct 50 ms 468 KB Output is correct
22 Correct 62 ms 776 KB Output is correct
23 Correct 109 ms 736 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 5 ms 492 KB Output is correct
26 Correct 5 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 3 ms 492 KB Output is correct
29 Correct 564 ms 532 KB Output is correct
30 Correct 457 ms 440 KB Output is correct
31 Correct 563 ms 536 KB Output is correct
32 Correct 488 ms 536 KB Output is correct
33 Correct 450 ms 540 KB Output is correct
34 Correct 315 ms 544 KB Output is correct
35 Correct 401 ms 768 KB Output is correct
36 Correct 438 ms 772 KB Output is correct
37 Correct 477 ms 644 KB Output is correct
38 Correct 477 ms 532 KB Output is correct
39 Correct 353 ms 764 KB Output is correct
40 Correct 441 ms 640 KB Output is correct
41 Correct 342 ms 644 KB Output is correct
42 Correct 67 ms 628 KB Output is correct
43 Correct 109 ms 640 KB Output is correct
44 Correct 119 ms 544 KB Output is correct
45 Correct 171 ms 620 KB Output is correct
46 Correct 320 ms 544 KB Output is correct
47 Correct 282 ms 544 KB Output is correct
48 Correct 49 ms 700 KB Output is correct
49 Correct 56 ms 668 KB Output is correct