Submission #973528

#	Time	Username	Problem	Language	Result	Execution time	Memory
973528		PieArmy	Hard route (IZhO17_road)	C++17	0 / 100	4 ms	12908 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;}
#define int ll
int n;
ll dp[500001][3][2],ans=0,say=0;
vector<int>komsu[500001];

void ekle(int loc,int x,int from){
    if(x>dp[loc][0][0]){
        dp[loc][2][0]=dp[loc][1][0];
        dp[loc][2][1]=dp[loc][1][1];
        dp[loc][1][0]=dp[loc][0][0];
        dp[loc][1][1]=dp[loc][0][1];
        dp[loc][0][0]=x;
        dp[loc][0][1]=from;
    }
    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][1][0]=x;
        dp[loc][1][1]=from;
    }
    else if(x>dp[loc][2][0]){
        dp[loc][2][0]=x;
        dp[loc][2][1]=from;
    }
}

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

void dfs2(int pos,int root){
    if(root){
        ll x=dp[root][0][0]+1;
        if(dp[root][0][1]==pos){
            x=dp[root][1][0]+1;
        }
        ekle(pos,x,root);
    }
    ll sum=dp[pos][0][0]+dp[pos][1][0]+dp[pos][2][0];
    if(dp[pos][0][0]&&dp[pos][1][0]&&dp[pos][2][0]){
        for(int i=0;i<3;i++){
            ll res=dp[pos][i][0]*(sum-dp[pos][i][0]);
            if(ans<res){
                ans=res;
                say=1;
            }
            else if(ans==res){
                say++;
            }
        }
    }
    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);
    if(ans==0)say++;
    cout<<ans<<" "<<say;
}

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

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