Submission #442042

#	Time	Username	Problem	Language	Result	Execution time	Memory
442042		JovanB	Race (IOI11_race)	C++17	100 / 100	971 ms	173000 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 dist[1000005];
int grane[1000005];
stack <int> qq;
 
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{
            ctree[parent].push_back(v);
        }
        qq.push(v);
        for(auto pr : graf[v]){
            int c = pr.first;
            if(!bio[c]){
                q.push({c, v});
            }
        }
    }
}
 
void dfs3(){
    vector <int> vec[1000005];
    while(!qq.empty()){
        int cnt = 0;
        int v = qq.top();
        qq.pop();
        for(auto c : ctree[v]){
            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]){
            int 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]){
                int 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]){
                int a = dist[gg];
                int 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();
        }
        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();
    if(res == INF) return -1;
    return res;
}

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