| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726942 |
2023-04-19T15:51:43 Z |
grogu |
Torrent (COI16_torrent) |
C++14 |
|
412 ms |
26764 KB |
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;
#define maxn 300005
ll n,x,y;
vector<ll> g[maxn];
vector<ll> cur;
bool naso = 0;
void dfs1(ll u,ll p,ll en){
cur.pb(u);
if(u==en){naso = 1;return;}
for(ll s : g[u]){
if(s==p) continue;
dfs1(s,u,en);
if(naso) return;
}
cur.popb();
}
pll ans[maxn];
pll bad;
bool chk(ll x,ll y){
if(x==bad.fi&&y==bad.sc) return 1;
swap(x,y);
if(x==bad.fi&&y==bad.sc) return 1;
return 0;
}
ll dfs(ll u,ll p){
vector<ll> v;
for(ll s : g[u]){
if(s==p) continue;
if(chk(u,s)) continue;
v.pb(dfs(s,u));
}
sort(all(v));
reverse(all(v));
ll ans = 0;
for(ll i = 0;i<v.size();i++) ans = max(ans,v[i]+i+1);
return ans;
}
pll f(ll i){
if(i<=-1) return {llinf,llinf};
if(i>=cur.size()-1) return {llinf,llinf};
if(ans[i].fi!=-1) return ans[i];
bad = {cur[i],cur[i+1]};
return ans[i] = {dfs(x,x),dfs(y,y)};
}
void tc(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> x >> y;
for(ll i = 1;i<=n-1;i++){
ll x,y; cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
dfs1(x,x,y);
ll l = 0,r = cur.size()-2,mid,rez = cur.size()-2;
for(ll i = 0;i<=cur.size()-2;i++) ans[i] = {-1,-1};
ans[cur.size()-1] = {llinf,llinf};
bool e = f(0).fi > f(0).fi;
while(l<=r){
ll mid = (l+r)/2;
if((f(mid).fi>f(mid).sc)==e) rez = mid,l = mid+1;
else r = mid-1;
}
ll ans = llinf;
for(ll i = rez;i<=rez+1;i++){
ans = min(ans,max(f(i).fi,f(i).sc));
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
int t; t = 1;
while(t--){
tc();
}
return 0;
}
/**
6 2 1
1 2
2 3
2 4
1 5
5 6
10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10
17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2
**/
Compilation message
torrent.cpp: In function 'long long int dfs(long long int, long long int)':
torrent.cpp:53:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(ll i = 0;i<v.size();i++) ans = max(ans,v[i]+i+1);
| ~^~~~~~~~~
torrent.cpp: In function 'std::pair<long long int, long long int> f(long long int)':
torrent.cpp:58:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(i>=cur.size()-1) return {llinf,llinf};
| ~^~~~~~~~~~~~~~
torrent.cpp: In function 'void tc()':
torrent.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(ll i = 0;i<=cur.size()-2;i++) ans[i] = {-1,-1};
| ~^~~~~~~~~~~~~~
torrent.cpp:72:31: warning: unused variable 'mid' [-Wunused-variable]
72 | ll l = 0,r = cur.size()-2,mid,rez = cur.size()-2;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
21996 KB |
Output is correct |
| 2 |
Correct |
379 ms |
24528 KB |
Output is correct |
| 3 |
Correct |
404 ms |
24828 KB |
Output is correct |
| 4 |
Correct |
400 ms |
26568 KB |
Output is correct |
| 5 |
Correct |
403 ms |
21324 KB |
Output is correct |
| 6 |
Correct |
365 ms |
21932 KB |
Output is correct |
| 7 |
Correct |
389 ms |
26764 KB |
Output is correct |
