Submission #536530

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
536530	2022-03-13 13:33:24	Stickfish	Railway (BOI17_railway)	C++17	100 / 100	290 ms	41900 KiB

railway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int MAXN = 1e5 + 123;
vector<int> edg[MAXN];
vector<int> redg[MAXN];
int rtnum[MAXN];
int depth[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
int to_root_add[MAXN];
pair<int, int> ghash(int v, int u) {
    if (v > u)
        return {u, v};
    return {v, u};
}
void dfsinit(int v, map<pair<int, int>, int>& mp) {
    tin[v] = timer++;
    if (redg[v].size()) {
        for (int j = 0;; ++j) { 
            int u = redg[v][j];
            if (j >= redg[u].size())
                break;
            redg[v].push_back(redg[u][j]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

railway.cpp: In function 'void dfsinit(int, std::map<std::pair<int, int>, int>&)':
railway.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             if (j >= redg[u].size())
      |                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'int lca(int, int)':
railway.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if (j < redg[u].size() && redg[u][j] != redg[v][j]) {
      |             ~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25