Submission #552541

#	Time	Username	Problem	Language	Result	Execution time	Memory
552541		StrawHatWess	Race (IOI11_race)	C++17	Compilation error	0 ms	0 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;
const int INF=2e9; 


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;
}



void getPaths(int u, int pre, int d, int e, vector<pi> &tmp;) {
    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, tmp);
    }
}

void solve(int u) {
    getSize(u, -1); 
    u = centroid(u, -1, sz[u]);
    done[u] = 1;
    
    vi vec; 

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

         
        if (!done[v]){
            vector<pi> tmp;

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


    for(int x: vec) ans[x]=INF; 
    ans[0]=0; 


    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:31:22: warning: unused variable 'w' [-Wunused-variable]
   31 |         int  v=it.F, w=it.S;
      |                      ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:40:22: warning: unused variable 'w' [-Wunused-variable]
   40 |         int  v=it.F, w=it.S;
      |                      ^
race.cpp: At global scope:
race.cpp:49:60: error: expected ')' before ';' token
   49 | void getPaths(int u, int pre, int d, int e, vector<pi> &tmp;) {
      |              ~                                             ^
      |                                                            )
race.cpp:49:61: error: expected unqualified-id before ')' token
   49 | void getPaths(int u, int pre, int d, int e, vector<pi> &tmp;) {
      |                                                             ^
race.cpp: In function 'void solve(int)':
race.cpp:91:22: warning: unused variable 'w' [-Wunused-variable]
   91 |         int  v=it.F, w=it.S;
      |                      ^