Submission #173369

#TimeUsernameProblemLanguageResultExecution timeMemory
173369achibasadzishviliHard route (IZhO17_road)C++14
0 / 100
2059 ms12152 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back #define N 500005 using namespace std; ll pp[N],n,cur,ind,cen; vector<ll>v[N]; pair<ll,ll>mx[N]; ll ans,ansraod; void dfs(ll x,ll par,ll dep){ pp[x] = par; if(dep > cur){ ind = x; cur = dep; } for(int i=0; i<v[x].size(); i++) if(v[x][i] != par) dfs(v[x][i] , x , dep + 1); } void go(ll x,ll par){ mx[x].f = 0; mx[x].s = 1; for(int i=0; i<v[x].size(); i++) if(v[x][i] != par){ int to = v[x][i]; go(to , x); if(mx[to].f > mx[x].f){ mx[x].f = mx[to].f; mx[x].s = 0; } if(mx[to].f == mx[x].f) mx[x].s += mx[to].s; } mx[x].f++; } void solve(ll x,ll par,ll zed){ ll mx1 = -1,mx2 = -1,ind = 0; for(int i=0; i<v[x].size(); i++) if(v[x][i] != par){ int to = v[x][i]; if(mx[to].f >= mx1){ ind = to; mx2 = mx1; mx1 = mx[to].f; } else if(mx[to].f > mx2)mx2 = mx[to].f; } mx1++; mx2++; for(int i=0; i<v[x].size(); i++) if(v[x][i] != par){ int to = v[x][i]; ll nex = 0; if(to == ind) nex = max(zed + 1 , mx2); else nex = max(zed + 1 , mx1); solve(to , x , nex); } mx1 = -1,mx2 = -1; ll ra1 = -1 , ra2 = 0 , raod = 0 , sum = 0 , minus = 0 , in = 0; for(int i=0; i<v[x].size(); i++){ if(v[x][i] != par){ int to = v[x][i]; if(mx[to].f == mx[x].f - 1){ sum += mx[to].s; minus += (mx[to].s - 1) * mx[to].s / 2 + mx[to].s; raod++; in = to; } } } if(raod > 1){ ll namr = zed; if(namr * 2LL * (mx[x].f - 1) > ans){ ans = namr * 2LL * (mx[x].f - 1); ansraod = 0; } if(namr * 2LL * (mx[x].f - 1) == ans){ ansraod += (sum * sum - minus) / 2; } return; } for(int i=0; i<v[x].size(); i++){ if(v[x][i] != par){ int to = v[x][i]; if(to == in)continue; if(mx[to].f > ra1){ ra1 = mx[to].f; ra2 = 0; } if(mx[to].f == ra1){ ra2 += mx[to].s; } } } ll namr = zed; if(namr * (mx[x].f - 1 + ra1) > ans){ ans = namr * (mx[x].f - 1 + ra1); ansraod = 0; } if(namr * (mx[x].f - 1 + ra1) == ans){ ansraod += sum * ra2; } } int main(){ ios::sync_with_stdio(false); cin >> n; if(n == 2){ cout << 0 << " " << 1 << '\n'; return 0; } for(int i=1; i<n; i++){ int x,y; cin >> x >> y; v[x].pb(y); v[y].pb(x); } ind = 1; cur = 0; dfs(1 , 0 , 0); cur = 0; dfs(ind , 0 , 0); ll we = cur; cur = cur / 2; cen = ind; while(cur--){ cen = pp[cen]; } if(we % 2 == 0){ go(cen , 0); solve(cen , 0 , 0); ll x = cen; ll gan = 0 , sum = 0 , minus = 0; for(int i=0; i<v[x].size(); i++) if(v[x][i] != 0){ int to = v[x][i]; if(mx[to].f == mx[x].f - 1){ gan++; sum += mx[to].s; minus += (mx[to].s - 1) * mx[to].s / 2 + mx[to].s; continue; } } if(gan > 2){ ll namr = max(mx[x].f - 1 , 0LL); if(namr * 2LL * (mx[x].f - 1) > ans){ ans = namr * 2LL * (mx[x].f - 1); ansraod = 0; } if(namr * 2LL * (mx[x].f - 1) == ans){ ansraod += (sum * sum - minus) / 2; } } if(gan == 2){ while(true); } cout << ans << " " << ansraod << '\n'; return 0; } go(cen , pp[cen]); go(pp[cen] , cen); solve(cen , pp[cen] , mx[pp[cen]].f); solve(pp[cen] , cen , mx[cen].f); cout << ans << " " << ansraod << '\n'; return 0; }

Compilation message (stderr)

road.cpp: In function 'void dfs(long long int, long long int, long long int)':
road.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++)
                  ~^~~~~~~~~~~~
road.cpp: In function 'void go(long long int, long long int)':
road.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++)
                  ~^~~~~~~~~~~~
road.cpp: In function 'void solve(long long int, long long int, long long int)':
road.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++)
                  ~^~~~~~~~~~~~
road.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++)
                  ~^~~~~~~~~~~~
road.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++){
                  ~^~~~~~~~~~~~
road.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++){
                  ~^~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v[x].size(); i++)
                      ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...