Submission #973866

#	Time	Username	Problem	Language	Result	Execution time	Memory
973866		PieArmy	Hard route (IZhO17_road)	C++17	100 / 100	552 ms	98108 KiB

road

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n;
ll dp[500001][3][3],ans=0,say=1;
vector<int>komsu[500001];

void ekle(int loc,int x,ll cnt){
    if(x>dp[loc][0][0]){
        dp[loc][2][0]=dp[loc][1][0];
        dp[loc][2][1]=dp[loc][1][1];
        dp[loc][2][2]=dp[loc][1][2];
        dp[loc][1][0]=dp[loc][0][0];
        dp[loc][1][1]=dp[loc][0][1];
        dp[loc][1][2]=dp[loc][0][2];
        dp[loc][0][0]=x;
        dp[loc][0][1]=0;
        dp[loc][0][2]=0;
    }
    else if(x>dp[loc][1][0]){
        dp[loc][2][0]=dp[loc][1][0];
        dp[loc][2][1]=dp[loc][1][1];
        dp[loc][2][2]=dp[loc][1][2];
        dp[loc][1][0]=x;
        dp[loc][1][1]=0;
        dp[loc][1][2]=0;
        if(x==dp[loc][0][0]){
            dp[loc][1][1]=dp[loc][0][1];
            dp[loc][1][2]=dp[loc][0][2];
        }
    }
    else if(x>dp[loc][2][0]){
        dp[loc][2][0]=x;
        dp[loc][2][1]=0;
        dp[loc][2][2]=0;
        if(x==dp[loc][1][0]){
            dp[loc][2][1]=dp[loc][1][1];
            dp[loc][2][2]=dp[loc][1][2];
        }
    }
    for(int i=0;i<3;i++){
        if(x==dp[loc][i][0]){
            dp[loc][i][2]+=dp[loc][i][1]*cnt;
            dp[loc][i][1]+=cnt;
        }
    }
}

void dfs1(int pos,int root){
    dp[pos][0][1]=1;
    for(int x:komsu[pos]){
        if(x==root)continue;
        dfs1(x,pos);
        ekle(pos,dp[x][0][0]+1,dp[x][0][1]);
    }
}

void dfs2(int pos,int root){
    if(root){
        if(dp[root][0][0]-1==dp[pos][0][0]){
            ll y=dp[root][1][1];
            if(dp[root][1][0]-1==dp[pos][0][0]){
                y-=dp[pos][0][1];
            }
            ekle(pos,dp[root][1][0]+1,y);
        }
        else{
            ekle(pos,dp[root][0][0]+1,dp[root][0][1]);
        }
    }
    if(dp[pos][0][0]&&dp[pos][1][0]&&dp[pos][2][0]){
        ll art=0;
        if(dp[pos][1][0]==dp[pos][2][0]){
            art=dp[pos][1][2];
        }
        else{
            art=dp[pos][1][1]*dp[pos][2][1];
        }
        if(dp[pos][0][0]*(dp[pos][1][0]+dp[pos][2][0])>ans){
            ans=dp[pos][0][0]*(dp[pos][1][0]+dp[pos][2][0]);
            say=art;
        }
        else if(dp[pos][0][0]*(dp[pos][1][0]+dp[pos][2][0])==ans){
            say+=art;
        }
    }
    for(int x:komsu[pos]){
        if(x==root)continue;
        dfs2(x,pos);
    }
}

void code(){
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        komsu[a].pb(b);
        komsu[b].pb(a);
    }
    dfs1(1,0);
    dfs2(1,0);
    cout<<ans<<" "<<say;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();cout<<endl;}
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:117:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
road.cpp:117:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~

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