oj.uz

답안 #72643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72643 2018-08-26T13:14:02 Z bnahmad15 Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 614 ms 133816 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;
	id = 0;
	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);
			fix(id,one,two,node,prnt);
		}
		id++;
	}
	if(in != 1){
		++one;
		++two;
		return;
	}
	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:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(id < g[node].size() && g[node][id].first != 1){
        ~~~^~~~~~~~~~~~~~~~
mousetrap.cpp:59:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(id < g[node].size()){
        ~~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:69: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:72: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

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47320 KB Output is correct
2 Correct 44 ms 47336 KB Output is correct
3 Correct 45 ms 47412 KB Output is correct
4 Correct 42 ms 47488 KB Output is correct
5 Correct 42 ms 47532 KB Output is correct
6 Correct 40 ms 47656 KB Output is correct
7 Incorrect 46 ms 47656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 614 ms 133816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47320 KB Output is correct
2 Correct 44 ms 47336 KB Output is correct
3 Correct 45 ms 47412 KB Output is correct
4 Correct 42 ms 47488 KB Output is correct
5 Correct 42 ms 47532 KB Output is correct
6 Correct 40 ms 47656 KB Output is correct
7 Incorrect 46 ms 47656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47320 KB Output is correct
2 Correct 44 ms 47336 KB Output is correct
3 Correct 45 ms 47412 KB Output is correct
4 Correct 42 ms 47488 KB Output is correct
5 Correct 42 ms 47532 KB Output is correct
6 Correct 40 ms 47656 KB Output is correct
7 Incorrect 46 ms 47656 KB Output isn't correct
8 Halted 0 ms 0 KB -