oj.uz

Submission #94530

# Submission time Handle Problem Language Result Execution time Memory
94530 2019-01-19T21:55:00 Z jasony123123 Mousetrap (CEOI17_mousetrap) C++11
45 / 100
 938 ms 56196 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e12;
/****************************************************************/
const int MAXN = 1e6 + 1;
int N, T, M;
v<int> adj[MAXN];

bool findpath(v<int> &path, int cur, int goal, int par) {
	path.push_back(cur);
	if (cur == goal) return 1;
	for (auto c : adj[cur]) if (c != par) {
		if (findpath(path, c, goal, cur)) return 1;
		path.pop_back();
	}
	return 0;
}

ll moves(int x, int p) {
	v<ll> cdp = { 0,0 };
	int deg = 0;
	for (auto c : adj[x]) if (c != p) {
		cdp.push_back(moves(c, x));
		deg++;
	}
	sort(all(cdp), greater<ll>());
	return deg + cdp[1];
}

int main() {
	io();
	cin >> N >> T >> M;
	FOR(i, 0, N - 1) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b), adj[b].push_back(a);
	}
	v<int> path;
	findpath(path, M, T, -1);
//	darr(path, path.size());

	ll ans = moves(path[0], path[1]);

	FOR(i, 1, path.size() - 1) {
		ans += adj[path[i]].size() - 2;
	}
	cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23928 KB Output is correct
3 Correct 18 ms 23800 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 18 ms 23800 KB Output is correct
6 Correct 19 ms 23800 KB Output is correct
7 Correct 19 ms 23800 KB Output is correct
8 Correct 19 ms 23928 KB Output is correct
9 Correct 19 ms 23800 KB Output is correct
10 Correct 18 ms 23800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 55212 KB Output is correct
2 Correct 354 ms 52000 KB Output is correct
3 Correct 938 ms 56184 KB Output is correct
4 Correct 404 ms 39972 KB Output is correct
5 Correct 916 ms 56184 KB Output is correct
6 Correct 899 ms 56196 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23928 KB Output is correct
3 Correct 18 ms 23800 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 18 ms 23800 KB Output is correct
6 Correct 19 ms 23800 KB Output is correct
7 Correct 19 ms 23800 KB Output is correct
8 Correct 19 ms 23928 KB Output is correct
9 Correct 19 ms 23800 KB Output is correct
10 Correct 18 ms 23800 KB Output is correct
11 Incorrect 18 ms 23804 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23928 KB Output is correct
3 Correct 18 ms 23800 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 18 ms 23800 KB Output is correct
6 Correct 19 ms 23800 KB Output is correct
7 Correct 19 ms 23800 KB Output is correct
8 Correct 19 ms 23928 KB Output is correct
9 Correct 19 ms 23800 KB Output is correct
10 Correct 18 ms 23800 KB Output is correct
11 Correct 379 ms 55212 KB Output is correct
12 Correct 354 ms 52000 KB Output is correct
13 Correct 938 ms 56184 KB Output is correct
14 Correct 404 ms 39972 KB Output is correct
15 Correct 916 ms 56184 KB Output is correct
16 Correct 899 ms 56196 KB Output is correct
17 Incorrect 18 ms 23804 KB Output isn't correct
18 Halted 0 ms 0 KB -