oj.uz

Submission #93124

# Submission time Handle Problem Language Result Execution time Memory
93124 2019-01-06T14:36:10 Z Vardanyan Hard route (IZhO17_road) C++14
0 / 100
 20 ms 15992 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 500*1000+5;
vector<int> g[N];
int dist[N];
int par[N];
void dfs(int v,int p = -1){
    par[v] = p;
    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);
    }
}
map<long long,int> H;
long long mx = 0;
void calc(int v,int hard = N,int d = 0,int p = -1){
   if(p!=-1){
        for(int i = 0;i<g[p].size();i++){
            int to = g[p][i];
            if(to!=v && to!=par[p]){
                dist[v] = max(dist[v],dist[to]+2);
            }
        }
   }
   hard = min(hard,dist[v]);
   if(g[v].size() == 1 && p!=-1){
        long long now = (long long)hard*(long long)d;
        H[now]++;
        mx = max(mx,now);
   }
    for(int i = 0;i<g[v].size();i++){
        int to = g[v][i];
        if(to == p) continue;
        calc(to,hard,d+1,v);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    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(par,0,sizeof par);
            memset(dist,0,sizeof dist);
            dfs(i);
            calc(i);
        }
    }
    cout<<mx<<" "<<H[mx]/2<<endl;
	return 0;
}

Compilation message

road.cpp: In function 'void dfs(int, int)':
road.cpp:9: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:20:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<g[p].size();i++){
                       ~^~~~~~~~~~~~
road.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();i++){
                   ~^~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15992 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 15 ms 15992 KB Output is correct
4 Correct 13 ms 15992 KB Output is correct
5 Correct 15 ms 15968 KB Output is correct
6 Correct 15 ms 15992 KB Output is correct
7 Incorrect 20 ms 15976 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15992 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 15 ms 15992 KB Output is correct
4 Correct 13 ms 15992 KB Output is correct
5 Correct 15 ms 15968 KB Output is correct
6 Correct 15 ms 15992 KB Output is correct
7 Incorrect 20 ms 15976 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15992 KB Output is correct
2 Correct 16 ms 15992 KB Output is correct
3 Correct 15 ms 15992 KB Output is correct
4 Correct 13 ms 15992 KB Output is correct
5 Correct 15 ms 15968 KB Output is correct
6 Correct 15 ms 15992 KB Output is correct
7 Incorrect 20 ms 15976 KB Output isn't correct
8 Halted 0 ms 0 KB -