Submission #406905

#	Time	Username	Problem	Language	Result	Execution time	Memory
406905		rumen_m	Traffic (IOI10_traffic)	C++17	100 / 100	1335 ms	163904 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
vector <int> g[maxn];
long long p[maxn];
long long subsize[maxn];
long long sum = 0;
void dfs(int v, int par = -1)
{
    int i;
    subsize[v]=p[v];
    for(auto u:g[v])
    {
        if(u==par)continue;
        dfs(u,v);
        subsize[v]+=subsize[u];
    }
}
int n;
long long ans = -1, maxans = 3e9;
void solve(int v, int par = -1)
{
    long long maxs = 0,k;
    for(auto u:g[v])
    {
        if(subsize[u]>maxs){maxs = subsize[u],k=u;}
    }
    if(maxans>maxs)
    {
        maxans = maxs;
        ans = v;
    }
  //  cout<<v<<" "<<maxs<<endl;
    for(auto u:g[v])
    {
         if(par==u)continue ;
         int prev = subsize[v];
          subsize[v] = sum - subsize[u];
            solve(u,v);
            subsize[v] = prev;
    }




}
int LocateCentre(int N, int pp[], int S[], int D[]) {
  int i;
  n = N;
  for(i=0;i<N-1;i++)
  {
      g[S[i]].push_back(D[i]);
      g[D[i]].push_back(S[i]);
  }
  for(i=0;i<N;i++)
  {
      sum+=pp[i];
      p[i] = pp[i];
  }
  dfs(0);
  solve(0);
  return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int)':
traffic.cpp:11:9: warning: unused variable 'i' [-Wunused-variable]
   11 |     int i;
      |         ^
traffic.cpp: In function 'void solve(int, int)':
traffic.cpp:24:24: warning: variable 'k' set but not used [-Wunused-but-set-variable]
   24 |     long long maxs = 0,k;
      |                        ^

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25