Submission #79822

#	Time	Username	Problem	Language	Result	Execution time	Memory
79822		Pajaraja	Hard route (IZhO17_road)	C++17	0 / 100	14 ms	12156 KiB

road

#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
vector<int> g[MAXN];
long long pot,cnt,d[MAXN],k[MAXN];
void dfsD(int s,int f,int di)
{
	d[s]=di;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1);
}
int dfsp(int s,int f)
{
	int mx=0;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) mx=max(mx,dfsp(g[s][i],s));
	d[s]=mx+1;
	return mx+1;
}
void calc(int s,int f,long long mx,long long du)
{
	if(s!=f && g[s].size()==1)
	{
		if(du*mx==pot) cnt++;
		if(du*mx>pot) {pot=du*mx; cnt=1;}
		return;
	}
	int mxi=0;
	long long mx1=0,mx2=0;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
	calc(g[s][mxi],s,max(mx,mx2),du+1);
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && i!=mxi) calc(g[s][i],s,max(mx,mx1),du+1);
}
void dfs(int s,int f,long long du)
{
	if(g[s].size()==1 && s!=f) {k[s]=1; d[s]=1; return;}
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,du+1);
	int mxi=0;
	long long mx1=0,mx2=0;
	k[s]=0;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) k[s]+=k[g[s][i]];
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
	d[s]=mx1+1;
	long long tc=0;
	if(mx1==mx2)
	{
		tc=k[s]*k[s];
		for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) tc-=k[g[s][i]]*k[g[s][i]];
		tc/=2;
	}
	else
	{
		for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx2) tc+=k[g[s][i]];
		tc*=k[s];
	}
	if(mx2==0) return;
	if((mx1+mx2)*du>pot) {pot=(mx1+mx2)*du; cnt=0;}
	if((mx1+mx2)*du==pot) cnt+=tc;
}
int main()
{
	int n,u=1,v=1;
	scanf("%d",&n);
	for(int i=0;i<n-1;i++)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		g[t1].push_back(t2);
		g[t2].push_back(t1);
	}
	dfsD(1,1,0);
	for(int i=1;i<=n;i++) if(d[i]>d[u]) u=i;
	dfsD(u,u,0);
	for(int i=1;i<=n;i++) if(d[i]>d[v]) v=i;
	/*dfsp(u,u);
	calc(u,u,0,0);
	dfsp(v,v);
	calc(v,v,0,0);*/
	dfs(u,u,0);
	dfs(v,v,0);
	printf("%lld %lld",pot,cnt);
}

Compilation message (stderr)

road.cpp: In function 'void dfsD(int, int, int)':
road.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsD(g[s][i],s,di+1);
              ~^~~~~~~~~~~~
road.cpp: In function 'int dfsp(int, int)':
road.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) mx=max(mx,dfsp(g[s][i],s));
              ~^~~~~~~~~~~~
road.cpp: In function 'void calc(int, int, long long int, long long int)':
road.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
              ~^~~~~~~~~~~~
road.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
              ~^~~~~~~~~~~~
road.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && i!=mxi) calc(g[s][i],s,max(mx,mx1),du+1);
              ~^~~~~~~~~~~~
road.cpp: In function 'void dfs(int, int, long long int)':
road.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,du+1);
              ~^~~~~~~~~~~~
road.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
              ~^~~~~~~~~~~~
road.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) k[s]+=k[g[s][i]];
              ~^~~~~~~~~~~~
road.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
              ~^~~~~~~~~~~~
road.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx1) tc-=k[g[s][i]]*k[g[s][i]];
               ~^~~~~~~~~~~~
road.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) if(d[g[s][i]]==mx2) tc+=k[g[s][i]];
               ~^~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
road.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&t1,&t2);
   ~~~~~^~~~~~~~~~~~~~~~

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