제출 #846675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846675		vjudge1	Torrent (COI16_torrent)	C++17	100 / 100	314 ms	28568 KiB

torrent

#include <bits/stdc++.h>
#define quan160607 "BoundSeq"
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
const int inf = 2e9;
const ll oo = 1e18;
const int nmax = 3e5 + 5;
void start()
{
//    freopen(quan160607".inp","r",stdin);
//    freopen(quan160607".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a, b, vis[nmax];
int x, y;
vector<int> v[nmax];
queue<pii> q;
int valA[nmax], valB[nmax], h[nmax], p[nmax];
vector<int> road, roadA, roadB;
void pre_dfs(int u, int par)
{
    for(auto x : v[u])
    {
        if(x != par)
        {
            p[x] = u;
            h[x] = h[u] + 1;
            pre_dfs(x, u);
        }
    }
}

int find_lca(int a, int b)
{
    while(h[a] > h[b])
    {
        roadA.push_back(p[a]);
        a = p[a];
    }
    if(a == b) return a;
    while(p[a] != p[b])
    {
        roadA.push_back(p[a]);
        roadB.push_back(p[b]);
        a = p[a];
        b = p[b];
    }
    roadA.push_back(p[a]);
    return p[a];
}

int dp[nmax], ta, tb;
void dfs(int u, int par)
{
    vector<int> vv;
    for(auto x : v[u])
    {
        if((u == ta && x == tb) || (x == ta && u == tb) || (x == par))
            continue;
        dfs(x, u);
        vv.push_back(dp[x]);
    }
    if(vv.size() == 0) return;
    sort(vv.begin(), vv.end(), greater<int>());
    for(int i = 0; i < vv.size(); i++)
    {
        dp[u] = max(dp[u], vv[i] + i + 1);
//        cout << u << " " << vv[i] << " " << i + 1 << "\n";
    }
}
int main()
{
    start();
    cin >> n >> a >> b;
    for(int i = 1; i <= n - 1; i++)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    p[1] = 1;
    h[1] = 1;
    pre_dfs(1, 1);
    if(h[a] < h[b])
        swap(a, b);
    roadA.push_back(a);
    roadB.push_back(b);
    int lca = find_lca(a, b);
    for(int i = 0; i < roadA.size(); i++)
    {
        road.push_back(roadA[i]);
    }
    for(int i = roadB.size() - 1; i >= 0; i--)
    {
        if(roadB[i] == lca)
            continue;
        road.push_back(roadB[i]);
    }
//    for(auto x : road)
//        cout << x << " ";
//    cout << "\n";
    int mid, l = 0, r = road.size() - 2; // 0 1 2 3
    int ans = inf;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        ta = road[mid], tb = road[mid + 1];
        memset(dp, 0, sizeof(dp));
        dfs(a, a);
        dfs(b, b);
//        cout << mid << " " << dp[a] << " " << dp[b] << "\n";
        ans = min(ans, max(dp[a], dp[b]));
        if(dp[a] > dp[b])
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 0; i < vv.size(); i++)
      |                    ~~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0; i < roadA.size(); i++)
      |                    ~~^~~~~~~~~~~~~~
torrent.cpp:109:9: warning: unused variable 'mid' [-Wunused-variable]
  109 |     int mid, l = 0, r = road.size() - 2; // 0 1 2 3
      |         ^~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69