Submission #261202

#	Time	Username	Problem	Language	Result	Execution time	Memory
261202		tbzard	Race (IOI11_race)	C++14	100 / 100	679 ms	35940 KiB

race

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

vector<pii> g[200005];
bool vis[200005];
int sub[200005];
int nn = 0;
int ans = 1e9;

void dfs1(int u, int p){
    sub[u] = 1;
    nn++;
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i].fi;
        if(v == p || vis[v]) continue;
        dfs1(v, u);
        sub[u] += sub[v];
    }
}

int dfs2(int u, int p){
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i].fi;
        if(v == p || vis[v]) continue;
        if(sub[v] > nn/2) return dfs2(v, u);
    }
    return u;
}

int best[1000005];
vector<pii> val;
void dfs3(int u, int p, int d, int c, int k){
    if(c > k) return;
    if(best[k-c] != -1) ans = min(ans, best[k-c] + d);
    val.eb(mp(c, d));
    for(int i=0;i<sz(g[u]);i++){
        int v = g[u][i].fi, w = g[u][i].se;
        if(v == p || vis[v]) continue;
        dfs3(v, u, d+1, c+w, k);
    }
}

void decompose(int u, int p, int k){
    nn = 0;
    dfs1(u, 0);
    int centroid = dfs2(u, 0);
    vis[centroid] = 1;

    vector<int> dist;
    best[0] = 0;
    dist.eb(0);
    for(int i=0;i<sz(g[centroid]);i++){
        int v = g[centroid][i].fi, w = g[centroid][i].se;
        if(v == p || vis[v]) continue;
        val.clear();
        dfs3(v, centroid, 1, w, k);
        for(int j=0;j<sz(val);j++){
            if(best[val[j].fi] == -1 || best[val[j].fi] > val[j].se) best[val[j].fi] = val[j].se;
            dist.eb(val[j].fi);
        }
    }
    for(int i=0;i<sz(dist);i++){
        best[dist[i]] = -1;
    }

    for(int i=0;i<g[centroid].size();i++){
        int v = g[centroid][i].fi;
        if(v == p || vis[v]) continue;
        decompose(v, centroid, k);
    }
}
int best_path(int n, int k, int h[][2], int l[]){
    for(int i=0;i<n-1;i++){
        g[h[i][0]].eb(mp(h[i][1], l[i]));
        g[h[i][1]].eb(mp(h[i][0], l[i]));
    }
    memset(best, -1, sizeof(best));
    decompose(0, -1, k);
    if(ans == 1e9) ans = -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs1(int, int)':
race.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++){
                 ~^~~~~~~~~~~~
race.cpp: In function 'int dfs2(int, int)':
race.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++){
                 ~^~~~~~~~~~~~
race.cpp: In function 'void decompose(int, int, int)':
race.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[centroid].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~

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