Submission #253283

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

race

#include<bits/stdc++.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 n, 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);
         }
      }
   }
}

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

   cin>> n >> K;
   for(int i = 1, u, v, w; i < n; i++)
   {
      cin>> u >> v >> w; u++; v++;  
      g[u].push_back({v,w});
      g[v].push_back({u,w});
   }

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

/*
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]
       int u = e.F, w = e.S;
                    ^
/tmp/ccqD0iqA.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc2VzNWF.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/cc2VzNWF.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