oj.uz

Submission #740564

# Submission time Handle Problem Language Result Execution time Memory
740564 2023-05-12T17:25:49 Z victor_gao Hard route (IZhO17_road) C++17
0 / 100
 34 ms 59060 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 500005
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,int>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 ((long long)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){
            if (have[p].count(dp1[i].x))
                dp[p]={dp1[i].x-1,have[p][dp1[i].x-1]};
            else dp[p]={dp1[i].x-1,0};
        }
        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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58996 KB Output is correct
2 Correct 32 ms 58984 KB Output is correct
3 Correct 34 ms 58916 KB Output is correct
4 Correct 31 ms 59004 KB Output is correct
5 Correct 29 ms 58956 KB Output is correct
6 Correct 32 ms 59032 KB Output is correct
7 Correct 30 ms 59000 KB Output is correct
8 Correct 32 ms 59060 KB Output is correct
9 Correct 31 ms 58948 KB Output is correct
10 Incorrect 31 ms 58968 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58996 KB Output is correct
2 Correct 32 ms 58984 KB Output is correct
3 Correct 34 ms 58916 KB Output is correct
4 Correct 31 ms 59004 KB Output is correct
5 Correct 29 ms 58956 KB Output is correct
6 Correct 32 ms 59032 KB Output is correct
7 Correct 30 ms 59000 KB Output is correct
8 Correct 32 ms 59060 KB Output is correct
9 Correct 31 ms 58948 KB Output is correct
10 Incorrect 31 ms 58968 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58996 KB Output is correct
2 Correct 32 ms 58984 KB Output is correct
3 Correct 34 ms 58916 KB Output is correct
4 Correct 31 ms 59004 KB Output is correct
5 Correct 29 ms 58956 KB Output is correct
6 Correct 32 ms 59032 KB Output is correct
7 Correct 30 ms 59000 KB Output is correct
8 Correct 32 ms 59060 KB Output is correct
9 Correct 31 ms 58948 KB Output is correct
10 Incorrect 31 ms 58968 KB Output isn't correct
11 Halted 0 ms 0 KB -