oj.uz

Submission #1085707

# Submission time Handle Problem Language Result Execution time Memory
1085707 2024-09-08T15:24:57 Z ShaShi Torrent (COI16_torrent) C++17
69 / 100
 641 ms 98252 KB 
#include <bits/stdc++.h>
 
// #define int long long
 
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9 + 7;


int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, flag2;
int arr[MAXN], sz[MAXN], A, B, par[MAXN], C, dp[MAXN];
vector<int> adj[MAXN], vec[MAXN], anc;
vector<pii> edge[MAXN];


void DFSsz(int v) {
    for (int u:adj[v]) {
        if (u == par[v]) continue;

        par[u] = v;
        DFSsz(u);
    }
}


void DFS(int v, int p=-1) {
    vec[v].clear();

    for (int u:adj[v]) {
        if (u == p || u == C) continue;
        
        DFS(u, v); vec[v].pb(dp[u]);
    }

    sort(all(vec[v]), greater<int>()); dp[v] = 0;

    for (int i=0; i<vec[v].size(); i++) dp[v] = max(dp[v], vec[v][i]+i+1);
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> A >> B;

    for (int i=1; i<n; i++) {
        cin >> u >> v;

        adj[u].pb(v); adj[v].pb(u);
    }

    DFSsz(A);

    tmp = B;
    while (tmp != A) anc.pb(tmp), tmp = par[tmp];

    int l, r, mid, mid2;

    l = 0; r = anc.size()-1;

    C = anc[l]; DFS(A); flag = dp[A]; C = par[C]; DFS(B); flag = max(flag, dp[B]); ans = flag;
    C = anc[r]; DFS(A); flag = dp[A]; C = par[C]; DFS(B); flag = max(flag, dp[B]); ans = min(ans, flag);

    while (r-l > 1) {
        mid = l+(r-l+1)/3; mid2 = r-(r-l+1)/3;

        C = anc[mid]; DFS(A); flag = dp[A]; C = par[C]; DFS(B); flag = max(flag, dp[B]);
        C = anc[mid2]; DFS(A); flag2 = dp[A]; C = par[C]; DFS(B); flag2 = max(flag2, dp[B]);

        // cout << "! " << l << " " << r << " " << mid << " " << mid2 << endl;

        if (flag <= flag2) r = mid2;
        else l = mid;
    }

    C = anc[l]; DFS(A); flag = dp[A]; C = par[C]; DFS(B); flag = max(flag, dp[B]); ans = min(ans, flag);
    C = anc[r]; DFS(A); flag = dp[A]; C = par[C]; DFS(B); flag = max(flag, dp[B]); ans = min(ans, flag);

    cout << ans << endl;
    


    return 0;
}

Compilation message

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

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 70992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 93332 KB Output is correct
2 Correct 641 ms 95568 KB Output is correct
3 Correct 602 ms 95184 KB Output is correct
4 Correct 553 ms 97900 KB Output is correct
5 Correct 582 ms 93520 KB Output is correct
6 Correct 558 ms 93964 KB Output is correct
7 Correct 529 ms 98252 KB Output is correct