Submission #834265

#	Time	Username	Problem	Language	Result	Execution time	Memory
834265		emad234	Race (IOI11_race)	C++17	0 / 100	4 ms	5392 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 = 1e5 + 5;
vector<vector<pair<int,int>>>v;
map<int,int>mp[mxN];
int vis[mxN];
int n, k;
int sh[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 += x.second * mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S];
        for(auto x : mp[p[b]]) mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] += x.second;
        sh[p[a]]++;
      }else{
        for(auto x : mp[p[b]]) ans += x.second * mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S];
        for(auto x : mp[p[b]]) mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] += x.second;
      }
      p[b] = p[a];
    }
  }
  mp[p[u]][-sh[p[u]]]++;
  ans += mp[p[u]][k - sh[p[u]]];
}
int best_path(int N, int K, int H[][2], int L[])
{
  n = N;k = K;
  ans = 0;
  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]].push_back({H[i][1],L[i]});
    v[H[i][1]].push_back({H[i][0],L[i]});
  }
  dfs(1);
  return ans;
}

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