Submission #647700

#	Time	Username	Problem	Language	Result	Execution time	Memory
647700		Marceantasy	Race (IOI11_race)	C++17	100 / 100	517 ms	51024 KiB

race

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

#define ll long long
#define ar array

const int mxN = 1e6+5, M = 1e9+7; 
int n, k, sz[mxN], mxtree[mxN], ans; 
vector<pair<int, int>> adj[mxN];
vector<int> new_vis;
bool used[mxN];

int dfs(int u, int p = -1){
    sz[u] = 1;
    for(pair<int, int> v : adj[u]){
        if(v.second != p && !used[v.second]){
            sz[u] += dfs(v.second, u); 
        }
    }
    return sz[u];
}

int get_centroid(int u, int ms, int p = -1){ // u = node, ms = size of the current tree delimited by previous centroids, p = parent
    for(pair<int, int> v : adj[u]){
        if(v.second != p && !used[v.second]){
            if(sz[v.second]*2 > ms){
                return get_centroid(v.second, ms, u);
            }
        }
    }
    return u;
}

int flag[mxN], stamp[mxN];
int timestamp;

void solve(int u){
    ++timestamp;
    int sz_curr_tree = dfs(u);
    int centroid = get_centroid(u, sz_curr_tree);
    used[centroid] = 1;
    flag[0] = 0;
    stamp[0] = timestamp;
    // do something with the centroid 
        for(pair<int, int> v : adj[centroid]){
            if(used[v.second]) continue;
            if(v.first > k) continue;
            queue<int> q, d, p, l; 
            vector<int> cd1, cd2; 
            q.push(v.second); 
            d.push(v.first);
            l.push(1); 
            p.push(centroid);
            while(q.size()){
                int qf = q.front(); 
                int df = d.front();
                int lf = l.front();
                int pf = p.front();
                cd1.push_back(df); 
                cd2.push_back(lf);
                if(stamp[k-df] == timestamp) ans = min(flag[k-df] + lf, ans);
                q.pop();
                d.pop(); 
                l.pop(); 
                p.pop();
                for(pair<int, int> v2 : adj[qf]){
                    int pos = v2.second;
                    if(used[pos] || pos == pf) continue;
                    if(df+v2.first > k) continue;
                    q.push(v2.second); 
                    d.push(df+v2.first);
                    l.push(lf+1);
                    p.push(qf);
                }
            }
            for(int i = 0; i<cd1.size(); ++i){
                if(stamp[cd1[i]] != timestamp){
                    flag[cd1[i]] = cd2[i];
                    stamp[cd1[i]] = timestamp;
                }else{
                    flag[cd1[i]] = min(flag[cd1[i]], cd2[i]);
                }
            }
            
        }
        for(pair<int, int> v : adj[centroid]){
            if(used[v.second]) continue;
            solve(v.second);
        }
    // end that something with the centroid xdd
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K; 
    for(int i = 0; i<N-1; ++i){
        adj[H[i][0]].push_back({L[i], H[i][1]}); 
        adj[H[i][1]].push_back({L[i], H[i][0]}); 
    }
    ans = 1e9;
    solve(0);
    if(ans > 1e8) return -1;
    return ans;
}

/*
int main(){
    int _N, _K; 
    cin >> _N >> _K; 
    int _H[_N][2], _L[_N]; 
    for(int i = 0; i<_N-1; ++i){
        cin >> _H[i][0] >> _H[i][1];
    }
    for(int i = 0; i<_N-1; ++i){
        cin >> _L[i];
    }
    cout << best_path(_N, _K, _H, _L) << "\n";
}
*/
//https://oj.uz/problem/view/IOI11_race

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
race.cpp:76:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int i = 0; i<cd1.size(); ++i){
      |                            ~^~~~~~~~~~~

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