| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 697731 |
2023-02-10T23:57:49 Z |
vjudge1 |
Torrent (COI16_torrent) |
C++14 |
|
92 ms |
48672 KB |
#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
using namespace std;
namespace IO
{
const int SZ=1<<20;
char gchar()
{
static char buf[SZ];
static int i=SZ;
if(i==SZ)i=0,fread(buf,1,SZ,stdin);
return buf[i++];
}
void pchar(char c)
{
static char buf[SZ];
static int i=0;
if(c)buf[i++]=c;
if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
}
void pstr(string s,char end='\n')
{
for(char c:s)pchar(c);
pchar(end);
}
template<typename T>void read(T &u)
{
u=0;int f=1;
static char c;
while((c=gchar())>'9'||c<'0')if(c=='-')f=-1;
u=c-'0';
while((c=gchar())>='0'&&c<='9')
u=(u<<1)+(u<<3)+(c^48);
u*=f;
}
template<typename T,typename ...Args>void read(T &u,Args&...args){read(u),read(args...);}
template<typename T>void i_write(T u)
{
if(u>9)i_write(u/10);
pchar(u%10+'0');
}
template<typename T>void write(T u,char end='\n')
{
if(u<0)pchar('-'),u=-u;
if(u>9)i_write(u/10);
pchar(u%10+'0');
pchar(end);
}
}
using IO::read;
using IO::write;
const int N=3e5+10;
int n,rt,ort,cnt,fa[N],f[N],link[N];
vector<int>e[N],g[N],dp[N];
void dfs(int u)
{
for(int v:e[u])
if(v!=fa[u])fa[v]=u,dfs(v),g[u].push_back(f[v]);
sort(g[u].begin(),g[u].end(),greater<int>());
int s=0;
for(int v:g[u])s++,f[u]=max(f[u],v+s);
}
bool check(int x)
{
int l,r,tmp=x;
for(l=1;l<=cnt;l++)
{
int mx=1,flg=0;
for(int j=0;j<(int)dp[link[l]].size();j++)
if(dp[link[l]][j]>x){flg=1;break;}
else if(dp[link[l]][j]==x)mx=j+2;
if(flg){l--;break;}
x-=mx;
}
for(r=cnt;r;r--)
{
int mx=1,flg=0;
for(int j=0;j<(int)dp[link[r]].size();j++)
if(dp[link[r]][j]>tmp){flg=1;break;}
else if(dp[link[r]][j]==tmp)mx=j+2;
if(flg){r++;break;}
tmp-=mx;
}
return l+1>=r;
}
int main()
{
read(n,rt,ort);
for(int i=1,u,v;i<n;i++)
read(u,v),e[u].push_back(v),e[v].push_back(u);
dfs(rt),link[cnt=1]=ort;
for(int u=ort;u!=rt;u=fa[u])link[++cnt]=fa[u];
for(int i=1;i<=cnt;i++)
{
dp[link[i]]=g[link[i]];
if(i!=1)
{
for(int j=0;j<(int)dp[link[i]].size();j++)
if(dp[link[i]][j]==f[link[i-1]]){dp[link[i]].erase(dp[link[i]].begin()+j);break;}
}
int s=0;
for(int &x:dp[link[i]])s++,x+=s;
}
int l=0,r=n,mid,ans=n;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
return 0;
}
Compilation message
torrent.cpp: In function 'char IO::gchar()':
torrent.cpp:18:24: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | if(i==SZ)i=0,fread(buf,1,SZ,stdin);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
10 ms |
21460 KB |
Output is correct |
| 3 |
Correct |
13 ms |
21536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
43588 KB |
Output is correct |
| 2 |
Correct |
84 ms |
45228 KB |
Output is correct |
| 3 |
Correct |
92 ms |
47336 KB |
Output is correct |
| 4 |
Correct |
83 ms |
46808 KB |
Output is correct |
| 5 |
Correct |
81 ms |
43852 KB |
Output is correct |
| 6 |
Correct |
75 ms |
44536 KB |
Output is correct |
| 7 |
Correct |
87 ms |
48672 KB |
Output is correct |
