Submission #585835

#	Time	Username	Problem	Language	Result	Execution time	Memory
585835		FatihSolak	Torrent (COI16_torrent)	C++17	0 / 100	113 ms	22340 KiB

torrent

#include <bits/stdc++.h>
#define N 300005
using namespace std;
vector<int> adj[N];
bool on_path[N];
vector<int> path;
int par[N];
int maxi[N],pos[N];
int rem[N];
int n,a,b;
void dfs(int v){
    if(v == b){
        while(v){
            path.push_back(v);
            on_path[v] = 1;
            v = par[v];
        }
        return;
    }
    for(auto u:adj[v]){
        if(u == par[v])continue;
        par[u] = v;
        dfs(u);
    }
}
void dfs1(int v){
    vector<int> x;
    for(auto u:adj[v]){
        if(u == par[v])continue;
        par[u] = v;
        dfs1(u);
        if(!on_path[u])
            x.push_back(maxi[u]); 
    }
    sort(x.rbegin(),x.rend());
    for(int i = 0;i<x.size();i++){
        if(x[i] + i + 1 >= maxi[v]){
            maxi[v] = x[i] + i + i;
            pos[v] = i + 1;
        }
    }
}
bool ck(int x){
    for(auto u:path){
        rem[u] = 0;
    }
    rem[a] = rem[b] = x;
    int pt1 = 0,pt2 = path.size()-1;
    while(pt1 < pt2){
        int nw1 = rem[path[pt1]] - 1;
        if(maxi[path[pt1]] == rem[path[pt1]]){
            nw1 -= pos[path[pt1]];
        }
        int nw2 = rem[path[pt2]] - 1;
        if(maxi[path[pt2]] == rem[path[pt2]]){
            nw2 -= pos[path[pt2]];
        }
        if(nw1 >= nw2){
            rem[path[pt1 + 1]] = max(rem[path[pt1 + 1]],nw1);
            pt1++;
        }
        else{
            rem[path[pt2 - 1]] = max(rem[path[pt2 - 1]],nw2);
            pt2--;
        }
    }
    for(auto u:path){
        if(rem[u] < maxi[u]){
            return 0;
        }
    }
    return 1;
}
void solve(){
    cin >> n >> a >> b;
    for(int i = 1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(a);
    dfs1(a);
    int l = 0,r = n;
    while(l < r){
        int m = (l + r)/2;
        if(ck(m)){
            r = m;
        }
        else l = m + 1;
    }
    cout << l << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

Compilation message (stderr)

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

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69