Submission #130701

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
130701	2019-07-15T23:29:18 Z	jovan_b	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

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

using namespace std;

int k;

typedef long long ll;

vector <int> ctree[1000005];
vector <pair <int, int>> graf[1000005];
bool visited[1000005];
bool bio[1000005];
int sz[1000005];
int dir[1000005];
int rnk[1000005];
ll dist[1000005];
int grane[1000005];

int prvi;

void dfs1(int v){
    sz[v] = 1;
    visited[v] = 1;
    for(auto par : graf[v]){
        int c = par.first;
        if(!bio[c] && !visited[c]){
            dfs1(c);
            sz[v] += sz[c];
        }
    }
    visited[v] = 0;
}

int nadji(int v, int n, int par){
    for(auto pr : graf[v]){
        int c = pr.first;
        if(bio[c]) continue;
        if(c == par) continue;
        if(sz[c] > n/2) return nadji(c, n, v);
    }
    return v;
}

int mnn1[1000005];
int mnn2[1000005];

struct strukt{
    ll first;
    int second;
    int third;
};

vector <strukt> sons[1000005];

void dfs2(int v, ll dis, int brg, int root){
    visited[v] = 1;
    if(dis){
        sons[root].push_back({dis, brg, v});
    }
    for(auto pr : graf[v]){
        int c = pr.first;
        int x = pr.second;
        if(!visited[c] && !bio[c]){
            dfs2(c, dis+x, brg+1, root);
        }
    }
    visited[v] = 0;
}

void decompose(){
    queue <strukt> q;
    q.push({1, 0, 1});
    while(!q.empty()){
        int v = q.front().first;
        int parent = q.front().second;
        q.pop();
        dfs1(v);
        v = nadji(v, sz[v], 0);
        bio[v] = 1;
        rnk[v] = q.front().third;
        dfs2(v, 0, 0, v);
        if(!parent) prvi = v;
        else{
            dir[v] = parent;
            ctree[parent].push_back(v);
        }
        for(auto pr : graf[v]){
            int c = pr.first;
            if(!bio[c]){
                q.push({c, v, rnk[v]+1});
            }
        }
    }
}

const int INF = 100000000;
int res = INF;

void dfs3(int v){
    vector <int> vec[1000005];
    int cnt = 0;
    for(auto c : ctree[v]){
        dfs3(c);
        sons[c].push_back({0, 0, c});
        cnt++;
        for(auto pr : sons[c]) vec[cnt].push_back(pr.third);
        sons[c].clear();
    }
    for(auto pr : sons[v]){
        ll a = pr.first;
        int b = pr.second;
        int c = pr.third;
        dist[c] = a;
        grane[c] = b;
    }
    for(int i=1; i<=cnt; i++){
        for(auto gg : vec[i]){
            ll a = dist[gg];
            int b = grane[gg];
            if(a == k) res = min(res, b);
            else if(a < k){
                res = min(res, b + mnn1[k-a]);
            }
        }
        for(auto gg : vec[i]){
            ll a = dist[gg];
            ll b = grane[gg];
            if(a > k) continue;
            if(mnn1[a] >= b){
                mnn2[a] = mnn1[a];
                mnn1[a] = b;
            }
            else if(mnn2[a] > b){
                mnn2[a] = b;
            }
        }
    }
    for(auto pr : sons[v]){
        if(pr.first > k) continue;
        mnn1[pr.first] = mnn2[pr.first] = INF;
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    int n = N;
    k = K;
    for(int i=0; i<n-1; i++){
        int a = H[i][0] + 1;
        int b = H[i][1] + 1;
        graf[a].push_back({b, L[i]});
        graf[b].push_back({a, L[i]});
    }
    decompose();
    for(int i=1; i<=n; i++) graf[i].clear();

    for(int i=1; i<=1000000; i++){
        mnn1[i] = mnn2[i] = INF;
    }
    dfs3(prvi);
    if(res == INF) return -1;
    return res;
}

/*int main(){
    int N, K, H[1000005][2], L[1000005];
    cin >> N >> K;
    for(int i=0; i<N; i++){
        cin >> H[i][0] >> H[i][1] >> L[i];
    }
    cout << best_path(N, K, H, L);
}*/
/*
10 6
0 1 3
1 2 2
2 3 2
3 4 3
4 5 2
5 6 2
6 7 3
7 8 2
8 9 2
*/
/*
3 2
0 1 1
1 2 1
*/

Compilation message

race.cpp:1:10: fatal error: grader.h: No such file or directory
 #include "grader.h"
          ^~~~~~~~~~
compilation terminated.