Submission #292462

#	Time	Username	Problem	Language	Result	Execution time	Memory
292462		davooddkareshki	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include<bits/stdc++.h>
#include "race.h"

using namespace std;

typedef long long ll;
typedef long double ld;

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

const int maxn = 2e5+10;
const ll inf = 1e18+10;
const int mod = 1e9+7;
const int N = 2e7+10;

int K;
map<int,int> *mp[maxn];
int st[maxn], h[maxn], sum[maxn];
vector<pii> g[maxn];

void pfs(int v, int p = -1)
{
   st[v] = 1;
   for(auto e : g[v])
   {
      int u = e.F, w = e.S;
      if(u != p)
      {
         sum[u] = sum[v] + w;
         h[u] = h[v] + 1;

         pfs(u,v);
         st[v] += st[u];
      }
   }
}

ll ans = inf;
void dfs(int v, int p = -1)
{
   int big = -1;
   for(auto e : g[v])
   {
      int u = e.F;
      if(u != p)
      {
         dfs(u,v);
         if(big == -1) big = u;
         else if(st[u] > st[big]) big = u;
      }
   }

   if(big != -1) mp[v] = mp[big];
   else mp[v] = new map<int,int>;
   (*mp[v])[sum[v]] = h[v];

   if((*mp[v]).count(K+sum[v]))
      ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);

   for(auto e : g[v])
   {
      int u = e.F, w = e.S;
      if(u != p && u != big)
      {
         for(auto X : (*mp[u]))
         {
            int sm = X.F, Mn = X.S;
            if((*mp[v]).count(K-sm+2*sum[v]))
            {
               int road = Mn + (*mp[v])[K-sm] - 2 * h[v];
               ans = min(ans,road);
            }
         }

         for(auto X : (*mp[u]))
         {
            int sm = X.F, Mn = X.S;
            if(!(*mp[v]).count(sm)) (*mp[v])[sm] = Mn;
            else (*mp[v])[sm] = min((*mp[v])[sm], Mn);
         }
      }
   }
}

int best_path(int n, int k, int h[][2], int l[])
{
   //cin>> n >> K;
   K = k;
   for(int i = 0, u, v, w; i < n-1; i++)
   {
      //cin>> u >> v >> w;
      u = h[i][0], v = h[i][1], w = l[i];
      u++; v++;
      g[u].push_back({v,w});
      g[v].push_back({u,w});
   }

   pfs(1); dfs(1);
   if(ans == inf) return -1;
   else return ans;
}

//signed main()
//{
   //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//}

/*
4 3
0 1 1
1 2 2
1 3 4

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

Compilation message (stderr)

race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:66:20: warning: unused variable 'w' [-Wunused-variable]
   66 |       int u = e.F, w = e.S;
      |                    ^
/tmp/ccxY6dcT.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status