Submission #406902

#	Time	Username	Problem	Language	Result	Execution time	Memory
406902		rumen_m	Traffic (IOI10_traffic)	C++17	0 / 100	13 ms	23756 KiB

traffic

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

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int)':
traffic.cpp:10:9: warning: unused variable 'i' [-Wunused-variable]
   10 |     int i;
      |         ^
traffic.cpp: At global scope:
traffic.cpp:20:24: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+9' to '2147483647' [-Woverflow]
   20 | int ans = -1, maxans = 3e9;
      |                        ^~~
traffic.cpp: In function 'void solve(int, int)':
traffic.cpp:34:31: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |     subsize[v] = n - subsize[k];
      |                      ~~~~~~~~~^

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