Submission #79840

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
79840	2018-10-16 17:47:53	Pajaraja	Hard route (IZhO17_road)	C++17	100 / 100	1951 ms	172468 KiB

road

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
vector<int> g[MAXN];
int b,mb,u,v,in[MAXN],out[MAXN],c1,c2,n,p[MAXN];
long long pot,cnt,d[MAXN],k[MAXN],ds[2][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);
}
void dfsd(int s,int f,int ka,long long di)
{
  ds[ka][s]=di;
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfsd(g[s][i],s,ka,di+1);
}
int dfsp(int s,int f)
{
  int mx=0;
  in[c1++]=s;
  p[s]=f;
  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;
  out[c2++]=s;
  return d[s];
}
void calc(int s,int f,long long mx,long long du)
{
  if(s!=f && g[s].size()==1)
  {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

road.cpp: In function 'void dfsD(int, int, int)':
road.cpp:10: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 'void dfsd(int, int, int, long long int)':
road.cpp:15: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,ka,di+1);
              ~^~~~~~~~~~~~
road.cpp: In function 'int dfsp(int, int)':
road.cpp:22: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:37: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:38: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: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 && i!=mxi) calc(g[s][i],s,max(mx,mx1),du+1);
              ~^~~~~~~~~~~~
road.cpp: In function 'void dfs(int)':
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]]>mx1) {mx1=d[g[s][i]]; mxi=i;}
               ~^~~~~~~~~~~~
road.cpp:54: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) k[s]+=k[g[s][i]];
               ~^~~~~~~~~~~~
road.cpp:55: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(i!=mxi) mx2=max(mx2,(long long)d[g[s][i]]);
               ~^~~~~~~~~~~~
road.cpp:61:17: 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:66:17: 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:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
road.cpp:81: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: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48