oj.uz

Submission #72666

# Submission time Handle Problem Language Result Execution time Memory
72666 2018-08-26T13:55:02 Z bnahmad15 Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 1378 ms 256736 KB 
#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++;
	}
	while(id < g[node].size() && (g[node][id].first == -1 || g[node][id].second.second == prnt))
		++id;
}
void dfs(ll node,ll prnt,ll &one,ll &two,ll in){
	if(node == t)
		return;
	ll id = 0;
	if (in == 2)
		src = node;
	while(id < g[node].size()){
		fix(id,one,two,node,prnt);
		if(g[node][id].first == 0){
			++two;
			dfs(g[node][id].second.second,node,one,two,2);
			g[node][id].first = -1;
		}else{
			++two;
			dfs(g[node][id].second.second,node,one,two,1);
			return;
		}
	}
	if(in == 1){
		one += d[src] - d[node];
		two += d[src] - d[node];
	}
}
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

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:37:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(id < g[node].size() && (g[node][id].first == -1 || g[node][id].second.second == prnt))
        ~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs(ll, ll, ll&, ll&, ll)':
mousetrap.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(id < g[node].size()){
        ~~~^~~~~~~~~~~~~~~~
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("%lld%lld%lld",&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("%lld%lld",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47224 KB Output is correct
2 Correct 44 ms 47588 KB Output is correct
3 Correct 47 ms 47588 KB Output is correct
4 Correct 43 ms 47588 KB Output is correct
5 Correct 41 ms 47588 KB Output is correct
6 Correct 41 ms 47588 KB Output is correct
7 Correct 52 ms 47588 KB Output is correct
8 Runtime error 82 ms 94744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 180956 KB Output is correct
2 Correct 629 ms 180956 KB Output is correct
3 Runtime error 1378 ms 256736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47224 KB Output is correct
2 Correct 44 ms 47588 KB Output is correct
3 Correct 47 ms 47588 KB Output is correct
4 Correct 43 ms 47588 KB Output is correct
5 Correct 41 ms 47588 KB Output is correct
6 Correct 41 ms 47588 KB Output is correct
7 Correct 52 ms 47588 KB Output is correct
8 Runtime error 82 ms 94744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47224 KB Output is correct
2 Correct 44 ms 47588 KB Output is correct
3 Correct 47 ms 47588 KB Output is correct
4 Correct 43 ms 47588 KB Output is correct
5 Correct 41 ms 47588 KB Output is correct
6 Correct 41 ms 47588 KB Output is correct
7 Correct 52 ms 47588 KB Output is correct
8 Runtime error 82 ms 94744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -