Submission #415269

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
415269	2021-05-31 18:59:16	SirCovidThe19th	Hard route (IZhO17_road)	C++14	100 / 100	1346 ms	152612 KiB

road

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;
#define ll long long
#define c2(x) (x*(x-1))/2
struct dp{
    ll tot, sep, badComb, d;
};
const int mx = 5e5+5;
int n, root = -1; vector<int> adj[mx];
dp in[mx][3], out[mx]; pair<ll, ll> ans; 
void updIn(int c, int val, int inc){
    if (val == in[c][0].d) in[c][0].tot += inc, in[c][0].sep++, in[c][0].badComb += c2(inc);
    else if (val == in[c][1].d) in[c][1].tot += inc, in[c][1].sep++, in[c][1].badComb += c2(inc);
    else if (val == in[c][2].d) in[c][2].tot += inc, in[c][2].sep++, in[c][2].badComb += c2(inc);
    else if (val > in[c][0].d) in[c][2] = in[c][1], in[c][1] = in[c][0], in[c][0] = {inc, 1, c2(inc), val};
    else if (val > in[c][1].d) in[c][2] = in[c][1], in[c][1] = {inc, 1, c2(inc), val};
    else if (val > in[c][2].d) in[c][2] = {inc, 1, c2(inc), val};
}
void updOut(int node, int nxt){
    dp cmpIn = in[node][0];
    if (in[nxt][0].d+1 == in[node][0].d and in[node][0].sep == 1) cmpIn = in[node][1];
    if (cmpIn.d > out[node].d) out[nxt] = {cmpIn.tot, 1, c2(cmpIn.tot), cmpIn.d+1};
    else if (cmpIn.d < out[node].d) out[nxt] = {out[node].tot, 1, c2(out[node].tot), out[node].d+1};
    else out[nxt] = {cmpIn.tot+out[node].tot, 1, c2(cmpIn.tot+out[node].tot), out[node].d+1};
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48