Submission #140408

#	Time	Username	Problem	Language	Result	Execution time	Memory
140408		jovan_b	Race (IOI11_race)	C++17	9 / 100	848 ms	262148 KiB

race

#include "race.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 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{
    int first;
    int second;
    int third;
};
 
const int INF = 1000001;
int res = INF;
 
vector <strukt> sons[1000005];
 
void dfs2(int v, int dis, int brg, int root){
    visited[v] = 1;
    if(v != root) 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, min(INF, dis+x), brg+1, root);
        }
    }
    visited[v] = 0;
}
 
void decompose(){
    queue <pair <int, int>> q;
    q.push({1, 0});
    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;
        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});
            }
        }
    }
}
 
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;
            }
        }
        vec[i].clear();
      	vec[i].shrink_to_fit();
    }
    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 1
7 8 2
8 9 2
*/
/*
3 2
0 1 1
1 2 1
*/

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