Submission #72628

#	Time	Username	Problem	Language	Result	Execution time	Memory
72628		bnahmad15	Mousetrap (CEOI17_mousetrap)	C++17	20 / 100	1269 ms	113192 KiB

mousetrap

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

Compilation message (stderr)

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

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