Submission #288560

#	Time	Username	Problem	Language	Result	Execution time	Memory
288560		BeanZ	Race (IOI11_race)	C++14	100 / 100	2666 ms	50516 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

#define ll int
#define endl '\n'
const int N = 2e5 + 5;
vector<pair<ll, ll>> node[N];
ll sz[N];
bool in[N];
ll res = 1e6;
ll K;
map<ll, ll> mem, tmp;
ll initsz(ll u, ll p){
        sz[u] = 1;
        for (auto j : node[u]){
                if (!in[j.first] || j.first == p) continue;
                initsz(j.first, u);
                sz[u] += sz[j.first];
        }
        return sz[u];
}
ll CT(ll u, ll p, ll S){
        for (auto j : node[u]){
                if (!in[j.first] || j.first == p) continue;
                if ((sz[j.first] * 2) > S) return CT(j.first, u, S);
        }
        return u;
}
void addtmp(ll d, ll e){
        if (tmp[d] == 0) tmp[d] = e;
        else tmp[d] = min(tmp[d], e);
}
void upd(ll d){
        if (mem[K - d] != 0) res = min(res, mem[K - d] + tmp[d]);
}
void dfs(ll u, ll p, ll d, ll e){
        if (d > K) return;
        addtmp(d, e);
        upd(d);
        for (auto j : node[u]){
                if (!in[j.first] || j.first == p) continue;
                dfs(j.first, u, d + j.second, e + 1);
        }
}
void addmem(ll d, ll e){
        if (mem[d] == 0) mem[d] = e;
        else mem[d] = min(mem[d], e);
}
void findCT(ll u){
        ll S = initsz(u, u);
        u = CT(u, u, S);
        in[u] = 0;
        mem.clear();
        for (auto j : node[u]){
                if (!in[j.first]) continue;
                tmp.clear();
                dfs(j.first, j.first, j.second, 1);
                if (tmp[K] != 0) res = min(res, tmp[K]);
                for (auto j : tmp){
                        addmem(j.first, j.second);
                }
        }
        for (auto j : node[u]){
                if (!in[j.first]) continue;
                findCT(j.first);
        }
}
ll best_path(int n, int k, int h[][2], int l[]){
        for (int i = 1; i < n; i++){
                node[h[i - 1][0] + 1].push_back({h[i - 1][1] + 1, l[i - 1]});
                node[h[i - 1][1] + 1].push_back({h[i - 1][0] + 1, l[i - 1]});
        }
        K = k;
        memset(in, 1, sizeof(in));
        findCT(1);
        if (res == 1e6) return -1;
        else return res;
}
/*
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
}
/*
*/

Compilation message (stderr)

race.cpp:90:1: warning: "/*" within comment [-Wcomment]
   90 | /*
      |

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