oj.uz

Submission #72647

# Submission time Handle Problem Language Result Execution time Memory
72647 2018-08-26T13:23:11 Z bnahmad15 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 1295 ms 133680 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++;
	}	
}
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);
	if(in == 1)
		src = node;
	while(id < g[node].size() && g[node][id].first != 1){
		if(g[node][id].second.second != prnt && g[node][id].first != -1){
			++two;
			dfs(g[node][id].second.second,node,one,two,2);
			one++;
			two++;
		}
		id++;
	}
	while(id < g[node].size()){
		if(g[node][id].second.second != prnt && g[node][id].first == 1){
			++two;
			dfs(g[node][id].second.second,node,one,two,1);
		}
		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

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:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(id < g[node].size() && g[node][id].first != 1){
        ~~~^~~~~~~~~~~~~~~~
mousetrap.cpp:54:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(id < g[node].size()){
        ~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:64: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:67: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 43 ms 47472 KB Output is correct
3 Correct 43 ms 47496 KB Output is correct
4 Correct 43 ms 47496 KB Output is correct
5 Correct 44 ms 47496 KB Output is correct
6 Correct 43 ms 47508 KB Output is correct
7 Correct 42 ms 47532 KB Output is correct
8 Correct 41 ms 47660 KB Output is correct
9 Correct 42 ms 47660 KB Output is correct
10 Correct 44 ms 47660 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 133680 KB Output is correct
2 Correct 554 ms 133680 KB Output is correct
3 Incorrect 1295 ms 133680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 43 ms 47472 KB Output is correct
3 Correct 43 ms 47496 KB Output is correct
4 Correct 43 ms 47496 KB Output is correct
5 Correct 44 ms 47496 KB Output is correct
6 Correct 43 ms 47508 KB Output is correct
7 Correct 42 ms 47532 KB Output is correct
8 Correct 41 ms 47660 KB Output is correct
9 Correct 42 ms 47660 KB Output is correct
10 Correct 44 ms 47660 KB Output is correct
11 Incorrect 44 ms 133680 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 43 ms 47472 KB Output is correct
3 Correct 43 ms 47496 KB Output is correct
4 Correct 43 ms 47496 KB Output is correct
5 Correct 44 ms 47496 KB Output is correct
6 Correct 43 ms 47508 KB Output is correct
7 Correct 42 ms 47532 KB Output is correct
8 Correct 41 ms 47660 KB Output is correct
9 Correct 42 ms 47660 KB Output is correct
10 Correct 44 ms 47660 KB Output is correct
11 Correct 621 ms 133680 KB Output is correct
12 Correct 554 ms 133680 KB Output is correct
13 Incorrect 1295 ms 133680 KB Output isn't correct
14 Halted 0 ms 0 KB -