oj.uz

Submission #72628

# Submission time Handle Problem Language Result Execution time Memory
72628 2018-08-26T12:49:33 Z bnahmad15 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 1269 ms 113192 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 = 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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 24048 KB Output is correct
3 Correct 23 ms 24048 KB Output is correct
4 Correct 23 ms 24060 KB Output is correct
5 Correct 23 ms 24060 KB Output is correct
6 Correct 25 ms 24060 KB Output is correct
7 Correct 24 ms 24060 KB Output is correct
8 Correct 23 ms 24092 KB Output is correct
9 Correct 22 ms 24216 KB Output is correct
10 Correct 25 ms 24216 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 92452 KB Output is correct
2 Correct 474 ms 98988 KB Output is correct
3 Incorrect 1269 ms 113192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 24048 KB Output is correct
3 Correct 23 ms 24048 KB Output is correct
4 Correct 23 ms 24060 KB Output is correct
5 Correct 23 ms 24060 KB Output is correct
6 Correct 25 ms 24060 KB Output is correct
7 Correct 24 ms 24060 KB Output is correct
8 Correct 23 ms 24092 KB Output is correct
9 Correct 22 ms 24216 KB Output is correct
10 Correct 25 ms 24216 KB Output is correct
11 Incorrect 26 ms 113192 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 24048 KB Output is correct
3 Correct 23 ms 24048 KB Output is correct
4 Correct 23 ms 24060 KB Output is correct
5 Correct 23 ms 24060 KB Output is correct
6 Correct 25 ms 24060 KB Output is correct
7 Correct 24 ms 24060 KB Output is correct
8 Correct 23 ms 24092 KB Output is correct
9 Correct 22 ms 24216 KB Output is correct
10 Correct 25 ms 24216 KB Output is correct
11 Correct 585 ms 92452 KB Output is correct
12 Correct 474 ms 98988 KB Output is correct
13 Incorrect 1269 ms 113192 KB Output isn't correct
14 Halted 0 ms 0 KB -