Submission #1161243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161243		estebanolmedo	Race (IOI11_race)	C++20	100 / 100	2338 ms	56632 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define forn(i,n) for(int i = 0; i < n; i++)
#define pb push_back

using namespace std;

typedef vector<int> vi;

const int MAXN = 2e5 + 20;
typedef pair<int,int> pii;
int sz[MAXN];
bool vis[MAXN];
vector<vi> adj;
int _K;
map<pii, int> edg;

const int INF = 1e8;

void dfs_sz(int u, int pa) {
        // cout << "dfs_sz: " << u << ' ' << pa << endl;
        sz[u] = 1;
        for(int v : adj[u]) if(v != pa && !vis[v]) {
                dfs_sz(v, u);
                sz[u] += sz[v];
        }
}

void go_children(int u, int pa, map<int, int>& curr, int depth = 1, int dis = 0) {
        int val = edg[{min(u, pa), max(u, pa)}] + dis;
        if(!curr.count(val)) curr[val] = INF;
        curr[val] = min(curr[val], depth);
        for(int v : adj[u]) if(v != pa && !vis[v]) {
                go_children(v, u, curr, depth + 1, val);
        }
}

void merge_maps(map<int,int>& tot, map<int,int>& curr) {
        for(auto& [val, cnt] : curr) {
                if(!tot.count(val)) {
                        tot[val] = cnt;
                }
                tot[val] = min(tot[val], cnt);
        }
}

int get_ans_curr(map<int,int>& tot, map<int,int>& curr) {
        int ans = INF;
        for(auto& [val, cnt] : curr) {
                int need = _K - val;
                if(tot.count(need)) {
                        ans = min(ans, tot[need] + cnt);
                }
        }
        return ans;
}


int get_centroid(int u) {
        // cout << "get_centroid: " << u << endl;
        for(int v : adj[u]) if(!vis[v]) {
                if(2*sz[v] > sz[u]) {
                        sz[u] -= sz[v];
                        sz[v] += sz[u];
                        return get_centroid(v);
                }
        }
        return u;
}

int solve_centroid(int cen) {
        map<int,int> tot;
        int ans = INF;
        for(int v : adj[cen]) if(!vis[v]) {
                map<int,int> curr;
                curr[0] = 0;
                go_children(v, cen, curr);
                ans = min(ans, get_ans_curr(tot, curr));
                merge_maps(tot, curr);
        }
        return ans;
}

int solve(int u) {
        dfs_sz(u, u);
        int centroid = get_centroid(u);
        // cout << "centroid: " << centroid << endl;
        vis[centroid] = true;

        int ans = solve_centroid(centroid);

        for(int v : adj[centroid]) if(!vis[v]) {
                ans = min(solve(v), ans);
        }
        return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
  _K = K;
  adj.resize(N);
  forn(i,N-1) {
          int u = H[i][0];
          int v = H[i][1];

          adj[u].pb(v);
          adj[v].pb(u);

          edg[{min(u,v), max(u,v)}] = L[i];
  }
  int ans = solve(0);
  if(ans == INF) return -1;
  return ans;
}

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