이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int dp[N];
int h[N];
bool viz[N];
vector<int> gr[N];
int par[N];
void first_dfs(int nod, int dad){
par[nod] = dad;
h[nod] = 1 + h[dad];
for(auto x:gr[nod]){
if(x != dad)
first_dfs(x, nod);
}
}
void dfs(int nod, int dad){
int nrvec = 0;
for(auto x:gr[nod]){
if(x == dad || viz[x] == true)
continue;
nrvec++;
dfs(x, nod);
}
if(nrvec == 1){
dp[nod] = 1;
return;
}
int m1 = 0, m2 = 0;
for(auto x:gr[nod]){
if(x == dad || viz[x])
continue;
if(nrvec + dp[x] > m1){
m2 = m1;
m1 = nrvec + dp[x];
}
else if(nrvec + dp[x] > m2){
m2 = nrvec + dp[x];
}
}
dp[nod] = m2;
}
int ans = 0;
int sm[N];
multiset<int> ms;
int last;
int solve(int nod){
viz[nod] = true;
if(par[nod] == 0)
return 0;
int sum = solve(par[nod]);
vector<int> vec;
for(auto x:gr[nod]){
if(viz[x] == false){
dfs(x, nod);
vec.push_back(dp[x]);
}
}
sort(vec.begin(), vec.end());
sum += gr[nod].size() - (par[nod] != 0) - (nod != last);
for(int i = 0; i < vec.size(); i++){
ms.insert(sum + vec[i]);
}
ms.insert(sum);
if(ms.size()){
auto itr = ms.rbegin();
ms.erase(ms.find(*itr));
}
if(last == nod && ms.size())
ans = *ms.rbegin();
return sum;
}
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n, root, m;
cin>>n>>root>>m;
for(int i =1 ; i<n; i++){
int x, y;
cin>>x>>y;
gr[x].push_back(y);
gr[y].push_back(x);
}
first_dfs(root, 0);
last = m;
solve(m);
cout<<ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
mousetrap.cpp: In function 'int solve(int)':
mousetrap.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < vec.size(); i++){
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |