oj.uz

Submission #585854

# Submission time Handle Problem Language Result Execution time Memory
585854 2022-06-29T12:59:50 Z FatihSolak Torrent (COI16_torrent) C++17
100 / 100
 113 ms 31888 KB 
#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 + 1;
            pos[v] = i + 1;
        }
    }
}
bool ck(int x){
    for(auto u:path){
        rem[u] = -1;
    }
    rem[a] = rem[b] = x;
    int pt1 = 0,pt2 = path.size()-1;
    while(pt1  + 1< 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]] = nw1;
        }
        else rem[path[--pt2]] = nw2;
    }
    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

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
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 22364 KB Output is correct
2 Correct 107 ms 28428 KB Output is correct
3 Correct 113 ms 31140 KB Output is correct
4 Correct 107 ms 29648 KB Output is correct
5 Correct 109 ms 26688 KB Output is correct
6 Correct 105 ms 27372 KB Output is correct
7 Correct 99 ms 31888 KB Output is correct