Submission #834556

#	Time	Username	Problem	Language	Result	Execution time	Memory
834556		emad234	Race (IOI11_race)	C++17	0 / 100	10 ms	25684 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
const int mod = 1e9 + 7;
const int mxN = 5e5 + 5;
#define MAX_N 500000
vector<vector<pair<int,int>>>v;
map<int,int>mp[mxN];
int vis[mxN];
int n, k;
int sh[mxN],sha[mxN];
int ans;
int p[mxN];
void dfs(int u){
  vis[u] = 1;
  for(auto ch : v[u]){
    if(!vis[ch.F]){
      dfs(ch.F);
      int a = u,b = ch.F;
      if(mp[p[a]].size() < mp[p[b]].size()){
        swap(a,b);
      }
      if(b == u){
        for(auto x : mp[p[b]]) {
            ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
        }
        for(auto x : mp[p[b]]){
          if(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]])
            mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]],x.second - 1 + sha[p[b]]);
          else mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = x.second - 1 + sha[p[b]];
        }
        sh[p[a]] += ch.S;
        sha[p[a]]++;
      }else{
        for(auto x : mp[p[b]]) {
            ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
        }
        for(auto x : mp[p[b]]){
          if(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]])
            mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]],x.second + 1 + sha[p[b]]);
          else mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = x.second + 1 + sha[p[b]];
        }
      }
      p[b] = p[a];
    }
  }
  mp[p[u]][-sh[p[u]]] = 0;
}
int best_path(int N, int K, int H[][2], int L[])
{
  n = N;k = K;
  ans = 2e9;
  memset(vis,0,sizeof vis);
  for(int i = 1;i <= n;i++){
    p[i] = i;
    sh[i] = 0;
    mp[i].clear();
  }
  v.clear();
  v.resize(n + 1);
  for (int i = 0;i < n - 1;i++){
    v[H[i][0] + 1].push_back({H[i][1] + 1,L[i]});
    v[H[i][1] + 1].push_back({H[i][0] + 1,L[i]});
  }
  dfs(1);
  if(ans == 2e9) ans = -1;
  return ans;
}

// static int N, K;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;
// inline
// void my_assert(int e) {if (!e) abort();}
// void read_input()
// {
//   int i;
//   my_assert(2==scanf("%d %d",&N,&K));
//   for(i=0; i<N-1; i++)
//     my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// }
// 
// main()
// {
//   read_input();
//   best_path(N,K,H,L);
//   cout<<ans;
//   return 0;
// }

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