oj.uz

Submission #54729

# Submission time Handle Problem Language Result Execution time Memory
54729 2018-07-04T21:04:47 Z milisav Torrent (COI16_torrent) C++17
100 / 100
 653 ms 22640 KB 
#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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 10 ms 7472 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 20164 KB Output is correct
2 Correct 653 ms 21320 KB Output is correct
3 Correct 577 ms 22308 KB Output is correct
4 Correct 561 ms 22308 KB Output is correct
5 Correct 625 ms 22308 KB Output is correct
6 Correct 597 ms 22308 KB Output is correct
7 Correct 581 ms 22640 KB Output is correct