oj.uz

Submission #531535

# Submission time Handle Problem Language Result Execution time Memory
531535 2022-03-01T02:34:39 Z Register Torrent (COI16_torrent) C++14
100 / 100
 148 ms 45092 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,rt,p,m,fa[N],f[N],id[N];
vector<int> e[N],v[N],t[N];
void dfs(int x){
	for(int y:e[x]) if(y!=fa[x]) fa[y]=x,dfs(y),v[x].push_back(f[y]);
	sort(v[x].begin(),v[x].end(),greater<int>());
	int s=0;
	for(int y:v[x]) f[x]=max(f[x],y+(++s));
}
bool chk(int x){
	int l,r,nx=x;
	for(l=1;l<=m;l++){
		bool fl=0;int mx=1;
		for(int j=0;j<t[id[l]].size();j++)
			if(t[id[l]][j]>x) {fl=1;break;}
			else if(t[id[l]][j]==x) mx=j+2;
		if(fl) {l--;break;}
		x-=mx;
	}
	for(r=m;r;r--){
		bool fl=0;int mx=1;
		for(int j=0;j<t[id[r]].size();j++)
			if(t[id[r]][j]>nx) {fl=1;break;}
			else if(t[id[r]][j]==nx) mx=j+2;
		if(fl) {r++;break;}
		nx-=mx;
	}
	return l+1>=r;
}
int main(){
	scanf("%d%d%d",&n,&rt,&p);
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
	dfs(rt);id[m=1]=p;
	for(int x=p;x!=rt;x=fa[x]) id[++m]=fa[x];
	for(int i=1;i<=m;i++){
		t[id[i]]=v[id[i]];
		if(i!=1)for(int j=0;j<t[id[i]].size();j++)
			if(t[id[i]][j]==f[id[i-1]]) {t[id[i]].erase(t[id[i]].begin()+j);break;}
		int s=0;
		for(int&x:t[id[i]]) x+=(++s);
	}
	int l=0,r=n,ans=n;
	while(l<=r){
		int mid=l+r>>1;
		if(chk(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}

Compilation message

torrent.cpp: In function 'bool chk(int)':
torrent.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int j=0;j<t[id[l]].size();j++)
      |               ~^~~~~~~~~~~~~~~~
torrent.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int j=0;j<t[id[r]].size();j++)
      |               ~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   if(i!=1)for(int j=0;j<t[id[i]].size();j++)
      |                       ~^~~~~~~~~~~~~~~~
torrent.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid=l+r>>1;
      |           ~^~
torrent.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d%d%d",&n,&rt,&p);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
torrent.cpp:34:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
      |                           ~~~~~^~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21452 KB Output is correct
2 Correct 11 ms 21452 KB Output is correct
3 Correct 11 ms 21444 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 39960 KB Output is correct
2 Correct 148 ms 41672 KB Output is correct
3 Correct 134 ms 43720 KB Output is correct
4 Correct 145 ms 43204 KB Output is correct
5 Correct 146 ms 40252 KB Output is correct
6 Correct 133 ms 41156 KB Output is correct
7 Correct 136 ms 45092 KB Output is correct