Submission #1004852
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
vector<int> t_parent;
vector<int> t_ord;
void tree_getorder(const vector<vi> &g, int root) {
int n = g.size();
t_parent.assign(n, -1);
t_ord.clear();
vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
t_ord.push_back(i);
for(int j = (int)g[i].size() - 1; j >= 0; j --) {
int c = g[i][j];
if(t_parent[c] == -1 && c != root) {
t_parent[c] = i;
stk.push_back(c);
}
}
}
}
template<typename Sum, typename Combine, typename Calc>
void freeTreeDP(const vector<int> &t_ord, const vector<int> &t_parent, vector<Sum> &downsum, vector<Sum> &upsum, Sum identity, Combine combine, Calc calc) {
int n = (int)t_ord.size();
vector<int> children(n, 0), childid(n, -1);
for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
int i = t_ord[ix], p = t_parent[i];
childid[i] = children[p] ++;
}
vector<vector<Sum>> prefix(n), suffix(n);
for(int i = 0; i < n; ++ i) {
prefix[i].assign(children[i] + 1, identity);
suffix[i].assign(children[i] + 1, identity);
}
downsum.assign(n, identity);
upsum.assign(n, identity);
for(int ix = (int)t_ord.size() - 1; ix >= 0; -- ix) {
int i = t_ord[ix], p = t_parent[i];
for(int j = 0; j < children[i]; ++ j)
prefix[i][j + 1] = combine(prefix[i][j], prefix[i][j + 1]);
for(int j = children[i]; j > 0; -- j)
suffix[i][j - 1] = combine(suffix[i][j - 1], suffix[i][j]);
if(p != -1) {
downsum[i] = calc(p, i, suffix[i][0]);
prefix[p][childid[i] + 1] = downsum[i];
suffix[p][childid[i]] = downsum[i];
}
}
downsum[t_ord[0]] = suffix[t_ord[0]][0];
for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
int i = t_ord[ix], p = t_parent[i];
Sum sum = suffix[p][childid[i] + 1];
sum = combine(sum, upsum[p]);
sum = combine(sum, prefix[p][childid[i]]);
upsum[i] = calc(i, p, sum);
}
}
struct Sum {
int maxNum;
Sum() : maxNum(0) {}
Sum operator+(const Sum &that) const {
Sum res;
res.maxNum = max(maxNum, that.maxNum);
return res;
}
};
int main() {
int N;
while(~scanf("%d", &N)) {
vector<vector<int> > g(N);
for(int i = 0; i < N - 1; ++ i) {
int u, v;
scanf("%d%d", &u, &v), -- u, -- v;
g[u].push_back(v);
g[v].push_back(u);
}
tree_getorder(g, 0);
int leafs = 0;
rep(i, N)
leafs += g[i].size() == 1;
vector<Sum> down, up;
freeTreeDP(t_ord, t_parent, down, up, Sum(), plus<Sum>(), [&](int from, int to, Sum sum) {
Sum res;
res.maxNum = sum.maxNum + (g[to].size() == 2);
return res;
});
int maxPath = 0;
rep(i, N) {
amax(maxPath, down[i].maxNum);
if(i != 0) amax(maxPath, up[i].maxNum );
}
int ans = leafs + maxPath;
printf("%d\n", ans);
}
return 0;
}
Submission Info
Submission Time
2016-12-01 20:34:10+0900
Task
K - Problem on Tree
User
anta
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
3341 Byte
Status
AC
Exec Time
94 ms
Memory
19072 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:86:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v), -- u, -- v;
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
100 / 100
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt
All
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
3 ms
256 KB
sample_02.txt
AC
3 ms
256 KB
subtask1_01.txt
AC
70 ms
15996 KB
subtask1_02.txt
AC
55 ms
12664 KB
subtask1_03.txt
AC
23 ms
5504 KB
subtask1_04.txt
AC
29 ms
6908 KB
subtask1_05.txt
AC
35 ms
8320 KB
subtask1_06.txt
AC
6 ms
1024 KB
subtask1_07.txt
AC
91 ms
18808 KB
subtask1_08.txt
AC
23 ms
5248 KB
subtask1_09.txt
AC
49 ms
11644 KB
subtask1_10.txt
AC
65 ms
15096 KB
subtask1_11.txt
AC
29 ms
7036 KB
subtask1_12.txt
AC
12 ms
2816 KB
subtask1_13.txt
AC
8 ms
1664 KB
subtask1_14.txt
AC
8 ms
1792 KB
subtask1_15.txt
AC
85 ms
19072 KB
subtask1_16.txt
AC
84 ms
19072 KB
subtask1_17.txt
AC
85 ms
19072 KB
subtask1_18.txt
AC
84 ms
19072 KB
subtask1_19.txt
AC
84 ms
19068 KB
subtask1_20.txt
AC
85 ms
19072 KB
subtask1_21.txt
AC
85 ms
19068 KB
subtask1_22.txt
AC
85 ms
19072 KB
subtask1_23.txt
AC
84 ms
19072 KB
subtask1_24.txt
AC
84 ms
19072 KB
subtask1_25.txt
AC
91 ms
19068 KB
subtask1_26.txt
AC
85 ms
19072 KB
subtask1_27.txt
AC
85 ms
19072 KB
subtask1_28.txt
AC
87 ms
19068 KB
subtask1_29.txt
AC
85 ms
19072 KB
subtask1_30.txt
AC
88 ms
19072 KB
subtask1_31.txt
AC
87 ms
19072 KB
subtask1_32.txt
AC
84 ms
19068 KB
subtask1_33.txt
AC
84 ms
19072 KB
subtask1_34.txt
AC
84 ms
19072 KB
subtask1_35.txt
AC
91 ms
19068 KB
subtask1_36.txt
AC
94 ms
19072 KB
subtask1_37.txt
AC
84 ms
19072 KB
subtask1_38.txt
AC
87 ms
19072 KB
subtask1_39.txt
AC
85 ms
19068 KB