제출 #446928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446928		SirCovidThe19th	Torrent (COI16_torrent)	C++14	100 / 100	612 ms	26520 KiB

torrent

#include <bits/stdc++.h>
using namespace std; 

const int mx = 3e5+5;

int n, a, b; vector<int> adj[mx], pth; bool stop = 0;

void getPath(int i, int p){
    if (!stop) pth.push_back(i);
    if (i == b) stop = 1;
    for (int nxt : adj[i]) if (nxt != p) getPath(nxt, i);
    if (!stop) pth.pop_back();
}int calc(int i, int p, int no){
    vector<int> vals; int ret = 0;
    for (int nxt : adj[i]) if (nxt != p and nxt != no) vals.push_back(calc(nxt, i, no));
    sort(vals.begin(), vals.end(), greater<int>());
    for (int x = 0; x < vals.size(); x++) ret = max(ret, vals[x]+x+1);
    return ret;
}void solve(){
    int low = 0, high = pth.size()-2, res = 1e9;
    while (low <= high){
        int mid = (low+high)/2; int x = calc(a, 0, pth[mid+1]), y = calc(b, 0, pth[mid]);
        res = min(res, max(x, y));
        (x < y) ? (low = mid+1) : (high = mid-1);
    }cout<<res<<endl;
}

int main(){
    cin >> n >> a >> b;
    for (int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }getPath(a, 0); solve();
}
 

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

torrent.cpp: In function 'int calc(int, int, int)':
torrent.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int x = 0; x < vals.size(); x++) ret = max(ret, vals[x]+x+1);
      |                     ~~^~~~~~~~~~~~~

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