Submission #410808

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
410808	2021-05-23 18:53:30	Malheiros	Railway (BOI17_railway)	C++17	100 / 100	129 ms	24524 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;
int n, m, k;
vector<pair<int, int>> graph[100001];
int tin[100001], tout[100001], timer = 0, anc[100001][20], p_edge[100001];
int chosen[50001], bit[100001];
void dfs(int node = 1, int parent = 0) {
  tin[node] = ++timer;
  for (int i = 1; i < 20; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];
  for (pair<int, int> i : graph[node]) if (i.first != parent) {
    anc[i.first][0] = node;
    p_edge[i.first] = i.second;
    dfs(i.first, node);
  }
  tout[node] = timer;
}
bool is_ancestor(int a, int b) {
  return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b) {
  if (is_ancestor(a, b)) return a;
  for (int i = 19; ~i; i--) {
    if (anc[a][i] && !is_ancestor(anc[a][i], b)) a = anc[a][i];
  }
  return anc[a][0];
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:55:10: warning: unused variable 'l' [-Wunused-variable]
   55 |   int s, l;
      |          ^

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