oj.uz

답안 #846646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846646 2023-09-08T08:13:57 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 316 ms 27376 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define task "test1"
#define minpos(x, y) (a[x] <= a[y] ? (x) : (y))
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;

int const nmax = 3e5+3;
int const mod = 1e9+7;
int const LG = 20;
int const base=3;

void open_file()
{
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
}

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int n,a,b,parent[nmax];
int use[nmax];
ll dp[nmax],ans=1e18;
vector<int> adj[nmax],v;

void dfs(int u,int par){
    for(auto x : adj[u]){
        if(x!=par){
            parent[x]=u;
            dfs(x,u);
        }
    }
}

void calc(int u,int par){
    vector<ll> time;
    dp[u]=0;
    for(auto x : adj[u]){
        if(x==use[u]) continue;
        if(x!=par){
            calc(x,u);
            time.push_back(dp[x]);
        }
    }
    sort(time.begin(),time.end(),greater<ll>());
    for(int i=0;i<time.size();i++) dp[u]=max(dp[u],time[i]+i+1);
}

bool check(int mid){
    use[v[mid]]=v[mid-1];
    use[v[mid-1]]=v[mid];
    calc(a,0);
    calc(b,0);
    use[v[mid]]=use[v[mid-1]]=0;
    ans=min(ans,max(dp[a],dp[b]));
    if(dp[a]<=dp[b]) return true;
    return false;
}

void input()
{
    cin >> n >> a >> b;
    for(int i=1;i<n;i++){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

void NGU()
{
    dfs(a,0);
    int tmp=b;
    while(tmp!=a){
        v.push_back(tmp);
        tmp=parent[tmp];
        if(tmp==a){
            v.push_back(a);
            break;
        }
    }
    reverse(v.begin(),v.end());
    int l=1,r=v.size()-1;
    while(l<=r){
        int m=l+r>>1;
        if(check(m)){
            l=m+1;
        }
        else r=m-1;
    }
    cout << ans;
}

int main()
{
    open_file();
    fast();
    input();
    NGU();
}
/*
*/

Compilation message

torrent.cpp: In function 'void calc(int, int)':
torrent.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<time.size();i++) dp[u]=max(dp[u],time[i]+i+1);
      |                 ~^~~~~~~~~~~~
torrent.cpp: In function 'void NGU()':
torrent.cpp:98:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |         int m=l+r>>1;
      |               ~^~
torrent.cpp: In function 'void open_file()':
torrent.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct

Subtask #2
69.0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 311 ms 23876 KB Output is correct
2 Correct 287 ms 25312 KB Output is correct
3 Correct 268 ms 26928 KB Output is correct
4 Correct 316 ms 26316 KB Output is correct
5 Correct 260 ms 23180 KB Output is correct
6 Correct 261 ms 24128 KB Output is correct
7 Correct 245 ms 27376 KB Output is correct