oj.uz

Submission #846092

# Submission time Handle Problem Language Result Execution time Memory
846092 2023-09-07T09:44:08 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 544 ms 30504 KB 
#include <bits/stdc++.h>

#define ll long long
const int nmax = 3e5 + 5;
const int mod = 1e9 + 7;
const int lg = 17;
const int M = 5;
const ll oo = 1e18;
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;

int a, b, n, f[nmax][2], par[nmax], ans = 1e9;
vector<int> adj[nmax], st;
bool vis[nmax];
void dfs(int u, int p){
    for(auto v : adj[u]){
        if(v == p) continue;
        par[v] = u;
        dfs(v, u);
    }
}

void dfs2(int u, int p, int k){
    vector<int> gg;
    for(auto v : adj[u]){
        if(vis[v] || v == p) continue;
        dfs2(v, u, k);
        gg.push_back(f[v][k]);
    }
    sort(gg.begin(), gg.end(), greater<int>());
    for(int i = 0; i < gg.size(); ++i) f[u][k] = max(f[u][k], gg[i] + i + 1);
}

bool check(int x, int y){
    memset(f, 0, sizeof f);
    vis[y] = 1; dfs2(a, -1, 0); vis[y] = 0;
    vis[x] = 1; dfs2(b, -1, 1); vis[x] = 0;
    ans = min(ans, max(f[a][0], f[b][1]));
    return f[a][0] > f[b][1];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
//    freopen("SwapCard.inp", "r", stdin);
//    freopen("SwapCard.out", "w", stdout);
    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, -1);
    int x = b;
    while(x != a){
        st.push_back(x);
        x = par[x];
    }
    st.push_back(a);
    int l = 0, r = st.size() - 2;
    while(l <= r){
        int mid = r + l >> 1;
        if(check(st[mid + 1], st[mid])) l = mid + 1;
        else r = mid - 1;
    }
    l = 0, r = st.size() - 2;
    while(l <= r){
        int mid = r + l >> 1;
        if(!check(st[mid + 1], st[mid])) r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;
}
/*
voi moi i tim
max pos sao cho
T[pos] >= a[i] && T[pos] < b[i]
*/

Compilation message

torrent.cpp: In function 'void dfs2(int, int, int)':
torrent.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i < gg.size(); ++i) f[u][k] = max(f[u][k], gg[i] + i + 1);
      |                    ~~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = r + l >> 1;
      |                   ~~^~~
torrent.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid = r + l >> 1;
      |                   ~~^~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 26940 KB Output is correct
2 Correct 544 ms 28512 KB Output is correct
3 Correct 468 ms 29868 KB Output is correct
4 Correct 488 ms 29292 KB Output is correct
5 Correct 463 ms 26808 KB Output is correct
6 Correct 431 ms 27092 KB Output is correct
7 Correct 458 ms 30504 KB Output is correct