Submission #35063

#	Time	Username	Problem	Language	Result	Execution time	Memory
35063		model_code	Hard route (IZhO17_road)	C++11	52 / 100	2000 ms	68648 KiB

road

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>

#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()
#define sz(a) (int)a.size()

const int inf = (1ll << 30) - 1;
const int maxn = (int) 1e5 + 10;

using namespace std;
vector<int> g[1000100];
int d[1000100];
int d2[1000100];
int n;
int dis, cnt;
int X;
void dfs(int v, int p = -1){
	d[v] = 0;
	d2[v] = 0;
	for(int i = 0; i < g[v].size(); i++){
		int to = g[v][i];
		if(to == p ) continue;
		dfs(to, v);
		if(d[v] < d[to] + 1){
			d2[v] = d[v];
			d[v] = d[to] + 1;
		}
		else if(d2[v] < d[to] + 1){
			d2[v] = d[to] + 1;
		}
	}
}

void get(int v, int p = -1, int mx = 0, int lev = 0){
	int ccnt = 0;
	for(int i = 0; i < g[v].size(); i++){
		int to = g[v][i];
		if(to == p) continue;
		ccnt++;
		int mx2 = mx;
		if(d[v] == d[to] + 1) mx2 = max(mx2, d2[v]);
		else mx2 = max(d[v], mx2);
		get(to, v, mx2, lev + 1);
	}
	if(ccnt > 0) return;
	if(X >= v) return;
	int cur = lev * mx; 
	if(dis < cur){
		dis = cur;
		cnt = 0;
	}
	if(cur == dis)
		cnt++;

}

void calc(int x){
	X = x;
	dfs(X);
	get(X);
}

void solve(){
	scanf("%d", &n);
	for(int i = 1, x, y; i < n; i++){
		scanf("%d%d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	if(n == 2){
		printf("0 1\n");
		return;
	}
	pii ans = mp(0, 0);
	for(int i = 1; i <= n; i++){
		if(g[i].size()==1){
			calc(i);
		}
	}
	printf("%d %d\n", dis, cnt);
}

int main () {
    int t=1;
    //scanf("%d", &t);
    for(int i=1; i <= t; i++){
      //printf("Case #%d\n", i);
      solve();
    }

    return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int)':
road.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++){
                   ^
road.cpp: In function 'void get(int, int, int, int)':
road.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++){
                   ^
road.cpp: In function 'void solve()':
road.cpp:92:6: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  pii ans = mp(0, 0);
      ^
road.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
road.cpp:84:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

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