oj.uz

Submission #834265

# Submission time Handle Problem Language Result Execution time Memory
834265 2023-08-22T12:25:22 Z emad234 Race (IOI11_race) C++17
0 / 100
 4 ms 5392 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5392 KB Output isn't correct
2 Halted 0 ms 0 KB -