Submission #292468

#	Time	Username	Problem	Language	Result	Execution time	Memory
292468		davooddkareshki	Race (IOI11_race)	C++17	9 / 100	152 ms	23800 KiB

race

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

using namespace std;

//#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 int inf = 1e9+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];
      }
   }
}

int 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;
}

/*int main()
{
}*/

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:63:20: warning: unused variable 'w' [-Wunused-variable]
   63 |       int u = e.F, w = e.S;
      |                    ^

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57