Submission #93159

#	Time	Username	Problem	Language	Result	Execution time	Memory
93159		Vardanyan	Hard route (IZhO17_road)	C++14	52 / 100	2059 ms	50120 KiB

road

#include <bits/stdc++.h>
using namespace std;
const int N = 500*1000+5;
vector<int> g[N];
int dist[N];
void dfs(int v,int p = -1){
    for(int i = 0;i<g[v].size();i++){
        int to = g[v][i];
        if(to == p) continue;
        dfs(to,v);
        dist[v] = max(dist[v],dist[to]+1);
    }
}
int H[5005*5005];
int mx = 0;
int n;
void calc(int v,int hard = 0,int d = 0,int p = -1){
    if((g[v].size() == 1 && d+1 == n)){
        hard = min(hard,dist[v]);
    }
   if(g[v].size() == 1 && p!=-1){
        int now = (int)hard*(int)d;
        H[now]++;
        mx = max(mx,now);
   }
   int mx1,mx2;
   mx1 = mx2 = 0;
   for(int i = 0;i<g[v].size();i++){
        int to = g[v][i];
        if(to == p) continue;
        if(dist[to]+1>mx1){
            mx1 = dist[to]+1;
        }
        else if(dist[to]+1>mx2){
            mx2 = dist[to]+1;
        }
   }
    for(int i = 0;i<g[v].size();i++){
        int to = g[v][i];
        if(to == p) continue;
        int h = -1;
        if(dist[to]+1 == mx1) h = mx2;
        else h = mx1;/*
        if(dist[v]>hard){
            for(int j = 0;j<g[v].size();j++){
                int too = g[v][j];
                if(too!=to && too!=p){
                    if(h == -1 || dist[too]+1>h) h = dist[too]+1;
                }
            }
        }*/
        int hardd = hard;
        if(h!=-1){
            hardd = max(hardd,h);
        }
        calc(to,hardd,d+1,v);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i = 1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1;i<=n;i++){
        if(g[i].size() == 1){
            memset(dist,0,sizeof dist);
            dfs(i);
            calc(i);
        }
    }
    //cout<<H[mx]<<endl;
    cout<<mx<<" "<<H[mx]/2<<endl;
	return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int)':
road.cpp:7:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();i++){
                   ~^~~~~~~~~~~~
road.cpp: In function 'void calc(int, int, int, int)':
road.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i<g[v].size();i++){
                  ~^~~~~~~~~~~~
road.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();i++){
                   ~^~~~~~~~~~~~

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