Submission #164591

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
164591	2019-11-21 19:18:15	dolphingarlic	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	184 ms	18040 KiB

catinatree

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>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
int n, d;
vector<int> graph[200001];
// dp: Maximum number of marked nodes in subtree of i
// to_root: Minimum length of path from a marked node to the root
// mn_dist: Maximum length of path from a marked node to the root after
// the erasing of another marked node
int dp[200001], to_root[200001], mn_dist[200001];
void dfs(int node = 0) {
    if (graph[node].size()) {
        int v = graph[node][0];
        dfs(v);
        if (to_root[v] + 1 >= d) {
            // We mark the root
            dp[node] = dp[v] + 1;
            to_root[node] = 0;
            mn_dist[node] = to_root[v] + 1;
        } else {
            // We don't
            dp[node] = dp[v];
            to_root[node] = to_root[v] + 1;
            mn_dist[node] = mn_dist[v] + 1;
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int)':
catinatree.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
catinatree.cpp:31:13:
         FOR(i, 1, graph[node].size()) {
             ~~~~~~~~~~~~~~~~~~~~~~~~    
catinatree.cpp:31:9: note: in expansion of macro 'FOR'
         FOR(i, 1, graph[node].size()) {
         ^~~
catinatree.cpp:44:17: warning: unused variable 'dss' [-Wunused-variable]
             int dss = mn_dist[node] + mn_dist[v] + 1;
                 ^~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49