Submission #72652

#	Time	Username	Problem	Language	Result	Execution time	Memory
72652		bnahmad15	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	631 ms	133540 KiB

mousetrap

#include <bits/stdc++.h>
#define forn(i,j,n) for(ll i = (ll)j;i<=(ll)n;i++)
#define nfor(i,j,n) for(ll i = (ll)j;i>=(ll)n;i--)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll N = 2000001,LOG = 17;
 
ll n,t,m,dep[N],d[N],src;
vector<pair<ll,pii> > g[N];
 
ll dfs1(ll u,ll prnt,ll depth){
	dep[u] = depth;
	d[u] = depth;
	ll ret = 0;
	forn(i,0,g[u].size() - 1){
		ll v = g[u][i].second.second;
		if(v == prnt)
			continue;
		ll tmp = dfs1(v,u,depth+1);
		ret = max(ret,tmp);
		dep[u] = max(dep[u],dep[v]);
		g[u][i].first = tmp;
		g[u][i].second.first = -dep[v];
	}
	if(u == t)
		return 1;
	return ret;
}
void fix(ll &id,ll &one,ll &two,ll &node,ll &prnt){
	while(one <= two && id < g[node].size() && g[node][id].first != 1){
		if(g[node][id].second.second != prnt && g[node][id].first != -1)
			one++;
		g[node][id].first = -1;
		id++;
	}	
}
void dfs(ll node,ll prnt,ll &one,ll &two,ll in){
	if(node == t)
		return;
	ll id = 0;
	fix(id,one,two,node,prnt);
	while(id < g[node].size()){
		if(g[node][id].second.second == prnt || g[node][id].first == -1){
			id++;
			continue;
		}
		if(g[node][id].first == 0){
			dfs(g[node][id].second.second,node,one,++two,2);
			one++;
			two++;
			fix(id,one,two,node,prnt);			
		}else{
			dfs(g[node][id].second.second,node,one,++two,1);
			return;
		}
		id++;
	}
}
int main(){
 
	scanf("%lld%lld%lld",&n,&t,&m);
	forn(i,1,n-1){
		ll u,v;
		scanf("%lld%lld",&u,&v);
		g[u].push_back(make_pair(0,make_pair(0,v)));
		g[v].push_back(make_pair(0,make_pair(0,u)));
	}
	dfs1(m,0,0);
	forn(i,1,n){
		sort(g[i].begin(),g[i].end());
//		forn(j,0,g[i].size()-1){
//			cout<<g[i][j].first<<" "<<g[i][j].second.first<<" "<<g[i][j].second.second<<endl;
//		}
//		cout<<endl;
	}
	ll one = 0,two = 0;
	dfs(m,0,one,two,1);
	cout<<one;
	return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'void fix(ll&, ll&, ll&, ll&, ll&)':
mousetrap.cpp:31:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(one <= two && id < g[node].size() && g[node][id].first != 1){
                      ~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs(ll, ll, ll&, ll&, ll)':
mousetrap.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(id < g[node].size()){
        ~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&t,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35