oj.uz

Submission #305044

# Submission time Handle Problem Language Result Execution time Memory
305044 2020-09-22T13:02:53 Z aZvezda Stations (IOI20_stations) C++14
100 / 100
 1145 ms 5912 KB 
#include "stations.h"
#include <vector>

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const int MAX_N = 1e5 + 10;
vector<int> g[MAX_N];
int lab[MAX_N], tme = 0;
void dfs(int x, int p, int d) {
    if(d % 2 == 0) {
        lab[x] = tme ++;
    }
    for(auto it : g[x]) {
        if(it == p) {continue;}
        dfs(it, x, d + 1);
    }
    if(d % 2 == 1) {
        lab[x] = tme ++;
    }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
    tme = 0;
    for(int i = 0; i < n; i ++) {
        g[i].resize(0);
    }
    for(int i = 0; i < n - 1; i ++) {
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    dfs(0, -1, 0);
    vector<int> ret;
    for(int i = 0; i < n; i ++) {
        ret.push_back(lab[i]);
    }
    return ret;
}

int find_next_station(int s, int t, vector<int> c) {
    vector<pair<int, int> > inout;
    if(s < c[0]) {
        int last = s;
        for(int i = 0; i < c.size() - 1; i ++) {
            int it = c[i];
            if(last + 1 <= t && t <= it) {
                return it;
            }
            last = it;
        }
        return c[c.size() - 1];
    } else {
        int last = s;
        for(int i = c.size() - 1; i > 0; i --) {
            int it = c[i];
            if(last - 1 >= t && t >= it) {
                return it;
            }
            last = it;
        }
        return c[0];
    }
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 5824 KB Output is correct
2 Correct 481 ms 5696 KB Output is correct
3 Correct 1025 ms 5536 KB Output is correct
4 Correct 795 ms 5384 KB Output is correct
5 Correct 696 ms 5512 KB Output is correct
6 Correct 692 ms 5632 KB Output is correct
7 Correct 592 ms 5676 KB Output is correct
8 Correct 7 ms 5504 KB Output is correct
9 Correct 10 ms 5540 KB Output is correct
10 Correct 5 ms 5600 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 5596 KB Output is correct
2 Correct 699 ms 5552 KB Output is correct
3 Correct 1111 ms 5504 KB Output is correct
4 Correct 704 ms 5640 KB Output is correct
5 Correct 776 ms 5504 KB Output is correct
6 Correct 576 ms 5504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 5624 KB Output is correct
2 Correct 524 ms 5640 KB Output is correct
3 Correct 1012 ms 5376 KB Output is correct
4 Correct 954 ms 5504 KB Output is correct
5 Correct 679 ms 5504 KB Output is correct
6 Correct 542 ms 5632 KB Output is correct
7 Correct 602 ms 5544 KB Output is correct
8 Correct 6 ms 5504 KB Output is correct
9 Correct 7 ms 5472 KB Output is correct
10 Correct 5 ms 5512 KB Output is correct
11 Correct 678 ms 5376 KB Output is correct
12 Correct 697 ms 5696 KB Output is correct
13 Correct 662 ms 5664 KB Output is correct
14 Correct 485 ms 5504 KB Output is correct
15 Correct 81 ms 5536 KB Output is correct
16 Correct 74 ms 5504 KB Output is correct
17 Correct 130 ms 5504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1023 ms 5504 KB Output is correct
2 Correct 810 ms 5504 KB Output is correct
3 Correct 662 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 4 ms 5376 KB Output is correct
7 Correct 657 ms 5504 KB Output is correct
8 Correct 1063 ms 5504 KB Output is correct
9 Correct 880 ms 5572 KB Output is correct
10 Correct 794 ms 5536 KB Output is correct
11 Correct 11 ms 5512 KB Output is correct
12 Correct 11 ms 5632 KB Output is correct
13 Correct 9 ms 5504 KB Output is correct
14 Correct 8 ms 5524 KB Output is correct
15 Correct 5 ms 5504 KB Output is correct
16 Correct 751 ms 5536 KB Output is correct
17 Correct 814 ms 5504 KB Output is correct
18 Correct 628 ms 5504 KB Output is correct
19 Correct 653 ms 5588 KB Output is correct
20 Correct 625 ms 5376 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 5912 KB Output is correct
2 Correct 613 ms 5548 KB Output is correct
3 Correct 1047 ms 5504 KB Output is correct
4 Correct 686 ms 5516 KB Output is correct
5 Correct 800 ms 5504 KB Output is correct
6 Correct 642 ms 5680 KB Output is correct
7 Correct 523 ms 5648 KB Output is correct
8 Correct 7 ms 5536 KB Output is correct
9 Correct 7 ms 5592 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 526 ms 5632 KB Output is correct
12 Correct 698 ms 5504 KB Output is correct
13 Correct 1145 ms 5512 KB Output is correct
14 Correct 769 ms 5640 KB Output is correct
15 Correct 771 ms 5504 KB Output is correct
16 Correct 514 ms 5576 KB Output is correct
17 Correct 707 ms 5504 KB Output is correct
18 Correct 546 ms 5648 KB Output is correct
19 Correct 553 ms 5632 KB Output is correct
20 Correct 611 ms 5664 KB Output is correct
21 Correct 91 ms 5376 KB Output is correct
22 Correct 101 ms 5504 KB Output is correct
23 Correct 157 ms 5632 KB Output is correct
24 Correct 10 ms 5536 KB Output is correct
25 Correct 10 ms 5504 KB Output is correct
26 Correct 10 ms 5512 KB Output is correct
27 Correct 8 ms 5504 KB Output is correct
28 Correct 4 ms 5408 KB Output is correct
29 Correct 594 ms 5500 KB Output is correct
30 Correct 625 ms 5376 KB Output is correct
31 Correct 587 ms 5504 KB Output is correct
32 Correct 624 ms 5504 KB Output is correct
33 Correct 562 ms 5504 KB Output is correct
34 Correct 422 ms 5632 KB Output is correct
35 Correct 449 ms 5628 KB Output is correct
36 Correct 605 ms 5632 KB Output is correct
37 Correct 538 ms 5640 KB Output is correct
38 Correct 681 ms 5632 KB Output is correct
39 Correct 534 ms 5552 KB Output is correct
40 Correct 620 ms 5728 KB Output is correct
41 Correct 559 ms 5656 KB Output is correct
42 Correct 93 ms 5544 KB Output is correct
43 Correct 133 ms 5520 KB Output is correct
44 Correct 149 ms 5504 KB Output is correct
45 Correct 167 ms 5632 KB Output is correct
46 Correct 474 ms 5592 KB Output is correct
47 Correct 352 ms 5632 KB Output is correct
48 Correct 87 ms 5664 KB Output is correct
49 Correct 77 ms 5656 KB Output is correct