Submission #384843

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
384843	2021-04-02 12:35:45	dolphingarlic	Pastiri (COI20_pastiri)	C++14	31 / 100	1097 ms	107448 KiB

pastiri

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>
typedef long long ll;
using namespace std;
vector<int> graph[500001];
int sheep[500001], to_sheep[500001], depth[500001], anc[500001][19], highest[500001];
bool guarded[500001];
void dfs(int node = 1, int parent = 0, int d = 0) {
    depth[node] = d;
    for (int i = 1; i < 19; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1];
    int h = node, dist = 1;
    for (int i = 18; ~i; i--) if (dist + (1 << i) == to_sheep[anc[h][i]]) {
        dist += (1 << i);
        h = anc[h][i];
    }
    highest[node] = h;
    for (int i : graph[node]) if (i != parent) {
        anc[i][0] = node;
        dfs(i, node, d + 1);
    }
}
void guard(int node) {
    guarded[node] = true;
    for (int i : graph[node]) if (!guarded[i] && to_sheep[node] == to_sheep[i] + 1) guard(i);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 0 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51