oj.uz

답안 #846607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846607 2023-09-08T06:49:49 Z danglayloi1 Torrent (COI16_torrent) C++17
69 / 100
 611 ms 38348 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const int nx=3e5+5;
int n, a, b, p[nx], ans, d, c, g, dp[nx];
bool vis[nx];
vector<int> adj[nx], tmp[nx];
map<pair<int, int>, int> mp;
vector<pair<int, int>> path;
void find(int u)
{
    if(u==b)
        return;
    vis[u]=1;
    for(int v:adj[u])
    {
        if(!vis[v])
        {
            p[v]=u;
            find(v);
        }
    }
}
void dfs(int u, int s, int t)
{
    vis[u]=1;
    for(int v:adj[u])
    {
        if(u==s && v==t)
            continue;
        if(u==t && v==s)
            continue;
        if(!vis[v])
        {
            dfs(v, s, t);
            tmp[u].emplace_back(dp[v]);
        }
    }
    int cur=0;
    sort(tmp[u].begin(), tmp[u].end(), greater<int>());
    for(int i = 0; i < tmp[u].size(); i++)
        cur=max(cur, tmp[u][i]+i+1);
    dp[u]=cur;
}
int cnt(int s, int t)
{
    memset(dp, 0x3f, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++)
        tmp[i].clear();
    dfs(a, s, t);
    dfs(b, s, t);
    return max(dp[a], dp[b]);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>a>>b;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    if(a==b)
        return cout<<cnt(a, a), 0;
    find(a);
    int s=b;
    while(s!=a)
    {
        path.emplace_back(s, p[s]);
        s=p[s];
    }
    d=0;
    c=path.size()-1;
    ans=inf;
    while(d<=c)
    {
        g=(d+c)/2;
        if(cnt(path[g].fi, path[g].se)<ans)
        {
            ans=cnt(path[g].fi, path[g].se);
            d=g+1;
        }
        else c=g-1;
    }
    d=0;
    c=path.size()-1;
    while(d<=c)
    {
        g=(d+c)/2;
        if(cnt(path[g].fi, path[g].se)<ans)
        {
            ans=cnt(path[g].fi, path[g].se);
            c=g-1;
        }
        else d=g+1;
    }
    cout<<ans;
}

Compilation message

torrent.cpp: In function 'void dfs(int, int, int)':
torrent.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < tmp[u].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
69.0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 611 ms 33868 KB Output is correct
2 Correct 595 ms 36176 KB Output is correct
3 Correct 494 ms 36056 KB Output is correct
4 Correct 519 ms 38324 KB Output is correct
5 Correct 544 ms 33832 KB Output is correct
6 Correct 468 ms 34120 KB Output is correct
7 Correct 362 ms 38348 KB Output is correct