oj.uz

답안 #72630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72630 2018-08-26T12:52:39 Z bnahmad15 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 1446 ms 102416 KB 
#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 = 2000001,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(in != 1){
		++one;
		++two;
		return;
	}
	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++;
	}
}
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

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:54: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:64: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:67: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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 48 ms 47460 KB Output is correct
3 Correct 47 ms 47460 KB Output is correct
4 Correct 54 ms 47460 KB Output is correct
5 Correct 51 ms 47460 KB Output is correct
6 Correct 58 ms 47460 KB Output is correct
7 Correct 55 ms 47460 KB Output is correct
8 Correct 48 ms 47460 KB Output is correct
9 Correct 54 ms 47460 KB Output is correct
10 Correct 47 ms 47516 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 567 ms 102416 KB Output is correct
2 Correct 483 ms 102416 KB Output is correct
3 Incorrect 1446 ms 102416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 48 ms 47460 KB Output is correct
3 Correct 47 ms 47460 KB Output is correct
4 Correct 54 ms 47460 KB Output is correct
5 Correct 51 ms 47460 KB Output is correct
6 Correct 58 ms 47460 KB Output is correct
7 Correct 55 ms 47460 KB Output is correct
8 Correct 48 ms 47460 KB Output is correct
9 Correct 54 ms 47460 KB Output is correct
10 Correct 47 ms 47516 KB Output is correct
11 Incorrect 52 ms 102416 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 48 ms 47460 KB Output is correct
3 Correct 47 ms 47460 KB Output is correct
4 Correct 54 ms 47460 KB Output is correct
5 Correct 51 ms 47460 KB Output is correct
6 Correct 58 ms 47460 KB Output is correct
7 Correct 55 ms 47460 KB Output is correct
8 Correct 48 ms 47460 KB Output is correct
9 Correct 54 ms 47460 KB Output is correct
10 Correct 47 ms 47516 KB Output is correct
11 Correct 567 ms 102416 KB Output is correct
12 Correct 483 ms 102416 KB Output is correct
13 Incorrect 1446 ms 102416 KB Output isn't correct
14 Halted 0 ms 0 KB -