이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct node_t {
int par;
vector<int> childs;
};
int n, a, b;
vector<vector<int>> adj;
vector<int> path;
vector<node_t> nodes;
class Solution {
public:
struct node_t {
int par, reqt;
vector<int> childs;
};
int ru, rv;
vector<node_t> nodes;
void rootTree(int cur, int par) {
node_t& u = nodes[cur];
if (par != -1) u.par = par;
for (int v : adj[cur]) {
if (v == par or (cur == ru and v == rv) or (cur == rv and v == ru)) continue;
u.childs.pb(v);
rootTree(v, cur);
}
}
void dfs(int cur) {
node_t& u = nodes[cur];
priority_queue<int> pq;
for (int v : u.childs) {
dfs(v);
pq.push(nodes[v].reqt);
}
int t = 1;
while (not pq.empty()) {
u.reqt = max(u.reqt, pq.top() + t);
pq.pop();
t++;
}
}
int ans() {
return max(nodes[a].reqt, nodes[b].reqt);
}
Solution(int ru, int rv) { // restricted vertices
this -> ru = ru;
this -> rv = rv;
nodes.resize(n + 1);
rootTree(a, -1);
rootTree(b, -1);
dfs(a);
dfs(b);
}
};
void rootTree(int cur, int par) {
node_t& u = nodes[cur];
if (par != -1) u.par = par;
for (int v : adj[cur]) {
if (v == par) continue;
u.childs.pb(v);
rootTree(v, cur);
}
}
void findPath(int cur) {
path.pb(cur);
if (cur == a) return;
findPath(nodes[cur].par);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b;
adj.resize(n + 1);
nodes.resize(n + 1);
int tu, tv, i;
for (i = 0; i < n - 1; i++) {
cin >> tu >> tv;
adj[tu].pb(tv);
adj[tv].pb(tu);
}
rootTree(a, -1);
findPath(b);
int l = 0, r = path.size() - 2, mid, res;
while (l < r - 1) {
mid = (l + r) / 2;
Solution left(path[mid], path[mid + 1]), right(path[mid + 1], path[mid + 2]);
if (left.ans() > right.ans()) l = mid;
else r = mid;
}
Solution sol(path[l], path[l + 1]);
cout << sol.ans();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
torrent.cpp: In function 'int main()':
torrent.cpp:98:42: warning: unused variable 'res' [-Wunused-variable]
98 | int l = 0, r = path.size() - 2, mid, res;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |