Submission #152977

#	Time	Username	Problem	Language	Result	Execution time	Memory
152977		gs18103	Race (IOI11_race)	C++14	100 / 100	1854 ms	55812 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define eb emplace_back
#define INF 2000000000

using namespace std;
typedef long long ll;
typedef pair <int, ll> pii;

bool chk[202020];
int c[202020], dep[202020];
vector <pii> g[202020];
vector <int> ct[202020];

int dfs(int x, int pa) {
    c[x] = 1;
    for(auto i : g[x]) {
        if(i.fi == pa) continue;
        c[x] += dfs(i.fi, x);
    }
    return c[x];
}

int find_cen(int x, int pa){
    int sz = 1, mx = 0, mxi;
    for(auto i : g[x]){
        if(chk[i.fi]) continue;
        sz += c[i.fi];
        if(c[i.fi] > mx){
            mx = c[i.fi];
            mxi = i.fi;
        }
    }
    if(mx <= sz/2) return x;
    c[x]= sz - mx;
    return find_cen(mxi, x);
}

int make_ct(int cur, int pa){
    int x = find_cen(cur, pa);
    chk[x] = true;
    for(auto i : g[x]){
        if(chk[i.fi]) continue;
        ct[x].eb(make_ct(i.fi, x));
    }
    return x;
}

int ans = INF;
ll k;
void get_ans(int x) {
    chk[x] = true;
    map <int, int> mp;
    mp.insert({0, 0});
    for(auto i : g[x]) {
        if(chk[i.fi]) continue;
        map <int, int> tmp;
        queue <pair <pii, int> > q;
        q.push({i, x});
        int cnt = 1;
        while(!q.empty()) {
            int sz = q.size();
            while(sz--) {
                int v = q.front().fi.fi, dis = q.front().fi.se, pa = q.front().se;
                q.pop();
                if(dis > k) continue;
                if(tmp.find(dis) == tmp.end()) tmp.insert({dis, cnt});
                if(mp.find(k-dis) != mp.end()) ans = min(ans, mp[k-dis] + cnt);
                for(auto i : g[v]) {
                    if(i.fi == pa || chk[i.fi]) continue;
                    q.push({{i.fi, dis+i.se}, v});
                }
            }
            cnt++;
        }
        for(auto it = tmp.begin(); it != tmp.end(); it++) {
            if(mp.find(it->fi) == mp.end()) mp.insert(*it);
            else mp[it->fi] = min(mp[it->fi], it->se);
        }
    }
    for(auto i : ct[x]) {
        if(chk[i]) continue;
        get_ans(i);
    }
}

int best_path(int n, int K, int H[][2], int L[]) {
    k = (ll)K;
    for(int i = 1; i < n; i++) {
        int u, v, w;
        u = H[i-1][0] + 1, v = H[i-1][1] + 1, w = L[i-1];
        g[u].eb(v, w), g[v].eb(u, w);
    }
    dfs(1, 0);
    int ctr = make_ct(1, 0);

    for(int i = 1; i <= n; i++) {
        chk[i] = false;
    }
    get_ans(ctr);
    if(ans == INF) return -1;
    else return ans;
}

Compilation message (stderr)

race.cpp: In function 'int find_cen(int, int)':
race.cpp:28:25: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int sz = 1, mx = 0, mxi;
                         ^~~
race.cpp: In function 'int make_ct(int, int)':
race.cpp:49:12: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return x;
            ^

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