oj.uz

Submission #740561

# Submission time Handle Problem Language Result Execution time Memory
740561 2023-05-12T17:23:40 Z victor_gao Hard route (IZhO17_road) C++17
52 / 100
 881 ms 262144 KB 
#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 500015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,fa[N];
long long ans=-1,cnt=0,a=0,b=0;
pii dp[N],dp1[N];
vector<int>g[N];
map<int,long long>have[N],son[N];
void dfs(int p,int lp){
    fa[p]=lp; dp[p]={0,0};
    if (g[p].size()==1){
        dp[p].y=1;
        return;
    }
    for (auto i:g[p]){
        if (i!=lp){
            dfs(i,p);
            if (dp[p].x==dp[i].x+1)
                dp[p].y+=dp[i].y;
            else dp[p]=max(dp[p],pii(dp[i].x+1,dp[i].y));
        }
    }
}
void dfs1(int p,int lp,pii val){
    dp1[p]={val.x+1,val.y};
    pii mx1=val,mx2={-1,0};
    for (auto i:g[p]){
        if (i!=lp){
            if (mx1.x==dp[i].x) mx1.y+=dp[i].y;
            else if (mx2.x==dp[i].x) mx2.y+=dp[i].y;
            else mx2=max(mx2,dp[i]);
            if (mx1<mx2) swap(mx1,mx2);
        }
    }
    mx1.x++; mx2.x++;
    for (auto i:g[p]){
        if (i!=lp){
            if (dp[i].x==mx1.x-1&&dp[i].y==mx1.y)
                dfs1(i,p,mx2);
            else if (dp[i].x==mx1.x-1)
                dfs1(i,p,{mx1.x,mx1.y-dp[i].y});
            else dfs1(i,p,mx1);
        }
    }
}
void relax(int x,int y){
    swap(x,y);
    if (x*y>ans){
        ans=x*y;
        a=x; b=y;
    }
}
void solve(){
    for (int j=1;j<=n;j++){
        vector<int>dep;
        for (auto i:g[j]){
            if (i!=fa[j])
                dep.push_back(dp[i].x+1);
        }
        if (dp1[j].y) dep.push_back(dp1[j].x);
        sort(dep.begin(),dep.end());
        if (dep.size()>2){
            int b1=dep.back(),b2=dep[dep.size()-2],b3=dep[dep.size()-3];
            for (int i=0;i<(int)(dep.size())-2;i++)
                relax(dep[i],(b2+b1));
            relax(b2,(b1+b3)); relax(b1,(b2+b3));
        }
    }
}
void dfs2(int p,int lp){
    //if (g[p].size()==1) return;
    for (auto i:g[p]){
        have[p][dp[i].x+1]+=dp[i].y;
        son[p][dp[i].x+1]++;
    }
    for (auto i:g[p]){
        auto [d,c]=dp[i]; d++;
        pii tmp=dp[p];
        have[p][d]-=c; son[p][d]--;
        int have_find=0;
        if (have[p].count(a-d)&&have[p][a-d]){
            son[p][a-d]--;
            if (son[p].count(b)&&son[p][b])
                cnt=(cnt+(long long)c*have[p][a-d]),have_find=1;
            son[p][a-d]++;
        }
        if (have[p].count(b-d)&&have[p][b-d]){
            son[p][b-d]--;
            if (son[p].count(a)&&son[p][a])
                cnt=(cnt+(long long)c*have[p][b-d]),have_find=1;
            son[p][b-d]++;
        }
        if (!have_find) dp[p]={dp1[i].x-1,have[p][dp1[i].x-1]};
        if (i!=lp)
            dfs2(i,p);
        dp[p]=tmp;
        have[p][d]+=c; son[p][d]++;
    }
}
signed main(){
    fast
    cin>>n;
    for (int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int root=0;
    for (int i=1;i<=n;i++){
        if (g[i].size()>1){
            root=i;
            break;
        }
    }
    dfs(root,0);
    dfs1(root,0,pii(-1,0));
    solve();
    dfs2(root,0);
    if (a==b) cnt/=2;
    if (ans<=0) cout<<0<<' '<<1<<'\n';
    else cout<<ans<<' '<<cnt/2<<'\n';
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58956 KB Output is correct
2 Correct 30 ms 58948 KB Output is correct
3 Correct 32 ms 59044 KB Output is correct
4 Correct 31 ms 59048 KB Output is correct
5 Correct 30 ms 58964 KB Output is correct
6 Correct 30 ms 59004 KB Output is correct
7 Correct 31 ms 58972 KB Output is correct
8 Correct 31 ms 58992 KB Output is correct
9 Correct 31 ms 59068 KB Output is correct
10 Correct 32 ms 58996 KB Output is correct
11 Correct 31 ms 58992 KB Output is correct
12 Correct 35 ms 59092 KB Output is correct
13 Correct 39 ms 59032 KB Output is correct
14 Correct 31 ms 59092 KB Output is correct
15 Correct 31 ms 59092 KB Output is correct
16 Correct 30 ms 58988 KB Output is correct
17 Correct 33 ms 59024 KB Output is correct
18 Correct 31 ms 59092 KB Output is correct
19 Correct 38 ms 58992 KB Output is correct
20 Correct 32 ms 59092 KB Output is correct
21 Correct 32 ms 59012 KB Output is correct
22 Correct 32 ms 58964 KB Output is correct
23 Correct 31 ms 59064 KB Output is correct
24 Correct 30 ms 59048 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58956 KB Output is correct
2 Correct 30 ms 58948 KB Output is correct
3 Correct 32 ms 59044 KB Output is correct
4 Correct 31 ms 59048 KB Output is correct
5 Correct 30 ms 58964 KB Output is correct
6 Correct 30 ms 59004 KB Output is correct
7 Correct 31 ms 58972 KB Output is correct
8 Correct 31 ms 58992 KB Output is correct
9 Correct 31 ms 59068 KB Output is correct
10 Correct 32 ms 58996 KB Output is correct
11 Correct 31 ms 58992 KB Output is correct
12 Correct 35 ms 59092 KB Output is correct
13 Correct 39 ms 59032 KB Output is correct
14 Correct 31 ms 59092 KB Output is correct
15 Correct 31 ms 59092 KB Output is correct
16 Correct 30 ms 58988 KB Output is correct
17 Correct 33 ms 59024 KB Output is correct
18 Correct 31 ms 59092 KB Output is correct
19 Correct 38 ms 58992 KB Output is correct
20 Correct 32 ms 59092 KB Output is correct
21 Correct 32 ms 59012 KB Output is correct
22 Correct 32 ms 58964 KB Output is correct
23 Correct 31 ms 59064 KB Output is correct
24 Correct 30 ms 59048 KB Output is correct
25 Correct 44 ms 61024 KB Output is correct
26 Correct 35 ms 61140 KB Output is correct
27 Correct 36 ms 60944 KB Output is correct
28 Correct 36 ms 61204 KB Output is correct
29 Correct 41 ms 61144 KB Output is correct
30 Correct 37 ms 61296 KB Output is correct
31 Correct 36 ms 61268 KB Output is correct
32 Correct 42 ms 61132 KB Output is correct
33 Correct 48 ms 61256 KB Output is correct
34 Correct 40 ms 61336 KB Output is correct
35 Correct 35 ms 61276 KB Output is correct
36 Correct 35 ms 61288 KB Output is correct
37 Correct 36 ms 61388 KB Output is correct
38 Correct 37 ms 61728 KB Output is correct
39 Correct 38 ms 61164 KB Output is correct
40 Correct 36 ms 60968 KB Output is correct
41 Correct 37 ms 60900 KB Output is correct
42 Correct 39 ms 60812 KB Output is correct
43 Correct 35 ms 60800 KB Output is correct
44 Correct 35 ms 60644 KB Output is correct
45 Correct 36 ms 60496 KB Output is correct
46 Correct 36 ms 60200 KB Output is correct
47 Correct 36 ms 60248 KB Output is correct
48 Correct 40 ms 60284 KB Output is correct

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58956 KB Output is correct
2 Correct 30 ms 58948 KB Output is correct
3 Correct 32 ms 59044 KB Output is correct
4 Correct 31 ms 59048 KB Output is correct
5 Correct 30 ms 58964 KB Output is correct
6 Correct 30 ms 59004 KB Output is correct
7 Correct 31 ms 58972 KB Output is correct
8 Correct 31 ms 58992 KB Output is correct
9 Correct 31 ms 59068 KB Output is correct
10 Correct 32 ms 58996 KB Output is correct
11 Correct 31 ms 58992 KB Output is correct
12 Correct 35 ms 59092 KB Output is correct
13 Correct 39 ms 59032 KB Output is correct
14 Correct 31 ms 59092 KB Output is correct
15 Correct 31 ms 59092 KB Output is correct
16 Correct 30 ms 58988 KB Output is correct
17 Correct 33 ms 59024 KB Output is correct
18 Correct 31 ms 59092 KB Output is correct
19 Correct 38 ms 58992 KB Output is correct
20 Correct 32 ms 59092 KB Output is correct
21 Correct 32 ms 59012 KB Output is correct
22 Correct 32 ms 58964 KB Output is correct
23 Correct 31 ms 59064 KB Output is correct
24 Correct 30 ms 59048 KB Output is correct
25 Correct 44 ms 61024 KB Output is correct
26 Correct 35 ms 61140 KB Output is correct
27 Correct 36 ms 60944 KB Output is correct
28 Correct 36 ms 61204 KB Output is correct
29 Correct 41 ms 61144 KB Output is correct
30 Correct 37 ms 61296 KB Output is correct
31 Correct 36 ms 61268 KB Output is correct
32 Correct 42 ms 61132 KB Output is correct
33 Correct 48 ms 61256 KB Output is correct
34 Correct 40 ms 61336 KB Output is correct
35 Correct 35 ms 61276 KB Output is correct
36 Correct 35 ms 61288 KB Output is correct
37 Correct 36 ms 61388 KB Output is correct
38 Correct 37 ms 61728 KB Output is correct
39 Correct 38 ms 61164 KB Output is correct
40 Correct 36 ms 60968 KB Output is correct
41 Correct 37 ms 60900 KB Output is correct
42 Correct 39 ms 60812 KB Output is correct
43 Correct 35 ms 60800 KB Output is correct
44 Correct 35 ms 60644 KB Output is correct
45 Correct 36 ms 60496 KB Output is correct
46 Correct 36 ms 60200 KB Output is correct
47 Correct 36 ms 60248 KB Output is correct
48 Correct 40 ms 60284 KB Output is correct
49 Runtime error 881 ms 262144 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -