Submission #552534

#	Time	Username	Problem	Language	Result	Execution time	Memory
552534		StrawHatWess	Race (IOI11_race)	C++17	21 / 100	3075 ms	14592 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;

typedef vector<int> vi;
typedef pair<int, int> pi;
#define F first
#define S second
#define PB push_back
const int maxn = 2e5 + 2;
const int maxk = 1000001;


void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}

//-----------------------------------

int n, k, sz[maxn], done[maxn], ans[maxk], tot=maxk;
vector<pi> adj[maxn];

void getSize(int u, int pre) {
    sz[u] = 1;
    for (auto it : adj[u]) {
        int  v=it.F, w=it.S;
        if (!done[v] && v != pre) {
            getSize(v, u); 
            sz[u] += sz[v];
        }
    }
}
int centroid(int u, int pre, int tot) {
    for (auto it : adj[u]) {
        int  v=it.F, w=it.S;
        if (v != pre && !done[v] && sz[v]*2 >= tot) 
            return centroid(v, u, tot);
    }
    return u;
}

vector<pi> tmp;

void getPaths(int u, int pre, int d, int e) {
    if (d <= k) {
        tot = min(tot, ans[k-d] + e);
        tmp.PB({d, e});
    }
    for (auto it : adj[u]) {
        int  v=it.F, w=it.S;
        if (!done[v] && v!=pre) 
            getPaths(v, u, d+w, e+1);
    }
}

void solve(int u) {
    getSize(u, -1); 
    u = centroid(u, -1, sz[u]);
    done[u] = 1;
    
    memset(ans, 0x3f, sizeof ans);
    ans[0] = 0;

    for (auto it : adj[u]) {
        int  v=it.F, w=it.S;

         
        if (!done[v]){
            tmp.clear();
            getPaths(v, u, w, 1);
        
            for (auto it : tmp){
                int d=it.F, e=it.S; 
                ans[d] = min(ans[d], e);
            }
        }
    }

    for (auto it : adj[u]) {
        int  v=it.F, w=it.S;
        if (!done[v]) solve(v);
    }
    
}


/*int main() {
    IO(); 


    cin >> n >> k;
    for (int u,v,w,i=0; i<n-1; i++) {
        cin >> u >> v >> w;
        adj[u].PB({v, w}); adj[v].PB({u, w});
    }

    solve(1);
    cout << (tot == maxk ? -1 : tot) << endl;
}
*/
int best_path(int n, int k, int H[][2], int L[]){
    ::n=n; ::k=k; 

    for (int u,v,w,i=0; i<n-1; i++) {
        u = H[i][0], v=H[i][1], w=L[i]; 
        adj[u].PB({v, w}); adj[v].PB({u, w});
    }

    solve(0);
    return (tot == maxk ? -1 : tot); 
}

Compilation message (stderr)

race.cpp: In function 'void getSize(int, int)':
race.cpp:30:22: warning: unused variable 'w' [-Wunused-variable]
   30 |         int  v=it.F, w=it.S;
      |                      ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:39:22: warning: unused variable 'w' [-Wunused-variable]
   39 |         int  v=it.F, w=it.S;
      |                      ^
race.cpp: In function 'void solve(int)':
race.cpp:84:22: warning: unused variable 'w' [-Wunused-variable]
   84 |         int  v=it.F, w=it.S;
      |                      ^

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