| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 246506 |
2020-07-09T13:25:58 Z |
vanic |
Torrent (COI16_torrent) |
C++14 |
|
729 ms |
29172 KB |
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <vector>
#include <assert.h>
using namespace std;
const int maxn=3e5+5;
int n, a, b;
vector < int > ms[maxn];
vector < int > put;
int val[maxn];
int jednako[maxn];
bitset < maxn > bio;
vector < int > svi;
bool dfs(int x, int prosl){
put.push_back(x);
if(x==b){
return 1;
}
for(int i=0; i<ms[x].size(); i++){
if(ms[x][i]!=prosl){
if(dfs(ms[x][i], x)){
return 1;
}
}
}
put.pop_back();
return 0;
}
int siri(int x, int prosl){
if(bio[x]){
return 0;
}
int sz=0;
for(int i=0; i<ms[x].size(); i++){
if(ms[x][i]!=prosl && !bio[ms[x][i]]){
sz++;
svi.push_back(siri(ms[x][i], x));
}
}
sort(svi.end()-sz, svi.end());
val[x]=1;
int br=1;
while(br<=sz){
if(val[x]<svi.back()+br){
val[x]=svi.back()+br;
jednako[x]=svi.back()-1;
}
else if(val[x]==svi.back()+br){
jednako[x]=svi.back()-1;
}
br++;
svi.pop_back();
}
// cout << "sirim " << x << " " << val[x] << " " << svi.size() << endl;;
return val[x];
}
int binary1(int usp){
int lo=1, hi=put.size()-1;
int mid;
while(lo<hi){
mid=(lo+hi)/2+1;
bio[put[mid]]=1;
// printf("ubi se\n");
// return 0;
if(siri(put[1], a)>usp){
hi=mid-1;
}
else{
lo=mid;
}
bio[put[mid]]=0;
}
return lo;
}
int binary2(int usp){
int lo=0, hi=put.size()-2;
int mid;
// printf("krecem %d\n", usp);
while(lo<hi){
mid=(lo+hi)/2;
bio[put[mid]]=1;
// printf("%d %d\n", mid, siri(put[put.size()-2], b));
if(siri(put[put.size()-2], b)>usp){
lo=mid+1;
}
else{
hi=mid;
}
bio[put[mid]]=0;
}
return lo;
}
int ternary(int lo, int hi){
int mid;
int val1, val2;
int val3, val4;
while(lo<hi){
mid=(lo+hi)/2+1;
bio[put[mid]]=1;
val1=siri(put[1], a);
bio[put[mid]]=0;
bio[put[mid-1]]=1;
val2=siri(put[put.size()-2], b);
bio[put[mid-1]]=0;
// printf("%d %d %d %d %d\n", mid, val1, val2, val3, val4);
if(val1>val2){
hi=mid-1;
}
else{
lo=mid;
}
}
bio[put[lo]]=1;
val1=siri(put[1], a);
val4=siri(put[put.size()-2], b);
bio[put[lo]]=0;
bio[put[lo-1]]=1;
val2=siri(put[put.size()-2], b);
bio[put[lo-1]]=0;
bio[put[lo+1]]=1;
val3=siri(put[1], a);
bio[put[lo+1]]=0;
return max(max(val[a], val[b]), min(max(val1, val2), max(val3, val4))); //nisam siguran za max(val[a], val[b]), al mislim da je ok
}
int main(){
scanf("%d%d%d", &n, &a, &b);
a--;
b--;
int c, d;
for(int i=0; i<n-1; i++){
scanf("%d%d", &c, &d);
c--;
d--;
ms[c].push_back(d);
ms[d].push_back(c);
}
dfs(a, a);
siri(a, put[1]);
siri(b, put[put.size()-2]);
int lo, hi;
lo=binary1(val[a]);
// return 0;
hi=binary2(val[b]);
int pri1, pri2;
int pos1=binary1(jednako[a])-1, pos2=binary2(jednako[b])+1;
bio[put[pos1]]=1;
pri1=max(val[a]-1, max(val[b], siri(put[put.size()-2], b)));
bio[put[pos1]]=0;
bio[put[pos2]]=1;
pri2=max(val[b]-1, max(val[a], siri(put[1], a)));
bio[put[pos2]]=0;
if(pos1+1>=pos2){
pri2=max(val[a]-1, val[b]-1);
}
// printf("%d %d\n", lo, hi);
// printf("%d %d\n", val[a], val[b]);
// printf("%d %d\n", pos1, pos2);
// printf("%d %d\n", jednako[a], jednako[b]);
int sol=1e9;
if(hi+1<=lo){
/* if(hi==0){
sol=min(sol, max(val[a]-1, val[b]));
}
if(lo==put.size()-1){
sol=min(sol, max(val[a], val[b]-1));
}*/
if(put.size()==2){
sol=max(val[a]-1, val[b]-1);
}
else{
sol=min(min(pri1, pri2), max(val[a], val[b]));
}
}
else{
sol=min(min(pri1, pri2), ternary(lo, hi+1));
}
printf("%d\n", sol);
return 0;
}
Compilation message
torrent.cpp: In function 'bool dfs(int, int)':
torrent.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ms[x].size(); i++){
~^~~~~~~~~~~~~
torrent.cpp: In function 'int siri(int, int)':
torrent.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<ms[x].size(); i++){
~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &c, &d);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
12 ms |
7424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
729 ms |
25772 KB |
Output is correct |
| 2 |
Correct |
704 ms |
27696 KB |
Output is correct |
| 3 |
Correct |
454 ms |
27740 KB |
Output is correct |
| 4 |
Correct |
614 ms |
29048 KB |
Output is correct |
| 5 |
Correct |
718 ms |
25472 KB |
Output is correct |
| 6 |
Correct |
534 ms |
25760 KB |
Output is correct |
| 7 |
Correct |
435 ms |
29172 KB |
Output is correct |
