Submission #394089

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
394089	2021-04-25 12:05:28	Sundavar	Railway (BOI17_railway)	C++14	100 / 100	366 ms	37000 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 <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int X = 18;
struct node{
    vector<pii> to;
    vector<int> father = *new vector<int>(X);
    int with = -1, cnt = 0, d = -1, out = 0;
    bool was = false;
};
vector<node> graph;
bool sortFunc(int a, int b){
    return graph[a].out < graph[b].out;
}
int in = 0;
void DFS(int curr, int father){
    graph[curr].was = true;
    graph[curr].father[0] = father;
    graph[curr].d = graph[father].d + 1;
    for(int i = 1; i < X; i++)
        graph[curr].father[i] = graph[graph[curr].father[i-1]].father[i-1];
    for(pii& to : graph[curr].to)
        if(!graph[to.first].was) 
            DFS(to.first, curr), graph[to.first].with = to.second;
    graph[curr].out = in++;
    graph[curr].was = false;
}
int lca(int a, int b){
    if(graph[a].d < graph[b].d) swap(a,b);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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