Submission #54729

#	Time	Username	Problem	Language	Result	Execution time	Memory
54729		milisav	Torrent (COI16_torrent)	C++17	100 / 100	653 ms	22640 KiB

torrent

#include<bits/stdc++.h>
using namespace std;
int n;
int a,b;
vector<int> s[300003];
int d[300003];
int c[300003];
int k;
stack<int> st;
bool dfs(int u) {
	int v;
	bool rv=false;
	for(int i=0;i<s[u].size();i++) {
		v=s[u][i];
		if(d[v]>d[u]+1) {
			d[v]=d[u]+1;
			if(dfs(v)) {
				rv=true;
				st.push(u);
			}
		}
	}
	if(u==b) {
		rv=true;
		st.push(u);
	}
	return rv;
}
int calc(int u) {
	int v;
	vector<int> c;
	for(int i=0;i<s[u].size();i++) {
		v=s[u][i];
		if(d[v]>d[u]+1) {
			d[v]=d[u]+1;
			c.push_back(calc(v));
		}
	}
	int rv=0;
	sort(c.begin(),c.end());
	int g=c.size();
	for(int i=0;i<g;i++) {
		rv=max(rv,c[i]+g-i);
	}
	return rv;
}
int init_dfs(int u,int f) {
	for(int i=0;i<n;i++) d[i]=n;
	d[u]=0;
	d[f]=0;
	return calc(u);
}
int main()
{
	int x,y;
	scanf("%d %d %d",&n,&a,&b);
	a--;
	b--;
	for(int i=0;i<n-1;i++) {
		scanf("%d %d",&x,&y);
		x--;
		y--;
		s[x].push_back(y);
		s[y].push_back(x);
	}
	for(int i=0;i<n;i++) d[i]=n;
	d[a]=0;
	dfs(a);
	while(st.size()>0) {
		c[k++]=st.top();
		st.pop();
	}
	int l=0,r=k-1;
	int sol=n;
	while(l<r) {
		int m=(l+r)>>1;
		x=init_dfs(a,c[m+1]);
		y=init_dfs(b,c[m]);
		sol=min(sol,max(x,y));
		if(x<y) l=m+1;
		else r=m;
	}
	x=init_dfs(a,c[l+1]);
	y=init_dfs(b,c[l]);
	sol=min(sol,max(x,y));
	x=init_dfs(a,c[r+1]);
	y=init_dfs(b,c[r]);
	sol=min(sol,max(x,y));
	printf("%d",sol);
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'bool dfs(int)':
torrent.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s[u].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int calc(int)':
torrent.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s[u].size();i++) {
              ~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:56: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:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69