oj.uz

Submission #1087292

# Submission time Handle Problem Language Result Execution time Memory
1087292 2024-09-12T12:56:50 Z nghiaaa Torrent (COI16_torrent) C++14
100 / 100
 241 ms 32144 KB 
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
#define fIlE "test."
const int mod = 998244353;
inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//mt19937 RAND(seed);
inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
inline int mul(int u,int v){return (ll)u*v%mod;}
const int N = 3e5 + 1;
vector<int> a[N];
int nxt[N];
ii edge[N];
int h[N];
int n, A, B;
bool del[N];
void fdfs(int u = 1, int par = 0)
{
    for (int i : a[u])
        if (i != par){
        {
            int v = edge[i].f == u ? edge[i].s : edge[i].f;
            nxt[v] = i;
            h[v] = h[u] + 1;
            fdfs(v, i);
        }
    }
}
vector<int> ok(int u, int v)
{
    vector<int> p, t;
    while(h[u] < h[v])
    {
        t.pb(nxt[v]);
        v = edge[nxt[v]].f == v ? edge[nxt[v]].s : edge[nxt[v]].f;
    }
    while(h[u] > h[v])
    {
        p.pb(nxt[u]);
        u = edge[nxt[u]].f == u ? edge[nxt[u]].s : edge[nxt[u]].f;
    }
    while(u != v)
    {
        t.pb(nxt[v]);
        v = edge[nxt[v]].f == v ? edge[nxt[v]].s : edge[nxt[v]].f;
        p.pb(nxt[u]);
        u = edge[nxt[u]].f == u ? edge[nxt[u]].s : edge[nxt[u]].f;
    }
    reverse(all(t));
    int _ = sz(p);
    p.resize(sz(p) + sz(t));
    copy(all(t), begin(p) + _);
    return p;
}
int f(int u, int par = 0)
{
    vector<int> cal;
    for (int i : a[u]) if (i != par && !del[i])
    {
        int v = edge[i].f == u ? edge[i].s : edge[i].f;
        cal.pb(f(v, i));
    }
    int ans = 0;
    sort(all(cal), greater<int>());
    forw(i, 0, sz(cal) - 1)
        ans = max(ans, i + 1 + cal[i]);
    return ans;
}
void solve()
{
    cin >> n >> A >> B;
    for (int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        edge[i] = mp(x, y);
        a[x].pb(i);
        a[y].pb(i);
    }
    fdfs();
    vector<int> List = ok(A, B);
    int l = 0, r = sz(List) - 1, ans = n;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        del[List[mid]] = 1;
        int la = f(A), lb = f(B);
        ans = min(ans, max(la, lb));
        if (la < lb)
            l = mid + 1;
        else r = mid - 1;
        del[List[mid]] = 0;
    }
    cout << ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(fIlE"inp", "r"))
        freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
    //time_t TIME_TU=clock();
    int t=1;
//    cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
torrent.cpp:116:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(fIlE"inp","r",stdin), freopen(fIlE"out","w",stdout);
      |                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 28756 KB Output is correct
2 Correct 234 ms 30736 KB Output is correct
3 Correct 241 ms 31504 KB Output is correct
4 Correct 240 ms 31980 KB Output is correct
5 Correct 238 ms 28156 KB Output is correct
6 Correct 214 ms 28496 KB Output is correct
7 Correct 211 ms 32144 KB Output is correct