## Submission #157193

# Submission time Handle Problem Language Result Execution time Memory
157193 2019-10-10T02:57:23 Z lyc Mousetrap (CEOI17_mousetrap) C++14
0 / 100
479 ms 103700 KB
```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 1e6+5;

int N, T, M, A, B;
vector<int> al[MX_N];
int w[MX_N], d[MX_N], pa[MX_N];
vector<ii> sub[MX_N];

void dfs(int u, int p) {
for (auto v : al[u]) if (v != p) {
pa[v] = u;
d[v] = d[u] + 1;
w[v] = w[u] + SZ(al[u])-1-(p!=0);
dfs(v,u);
}
if (SZ(al[u]) != 1) {
int a = 0, b = 0;
for (auto v : al[u]) if (v != p) {
if (w[v] > a) a = w[v];
else if (w[v] > b) b = w[v];
}
if (b) w[u] = b;
else ++w[u];
}
//cout << u << " (" << w[u] << ")\n";
}

int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);

cin >> N >> T >> M;
FOR(i,1,N-1){
cin >> A >> B;
al[A].push_back(B);
al[B].push_back(A);
}

dfs(T,0);
int lo = -1, hi = 2*N;
while (hi-lo > 1) {
int mid = (lo+hi)/2;

int p, u, i, b, bad = 0;
for (p = -1, u = M, i = 0, b = 0; pa[u] != 0; p = u, u = pa[u], ++i) {
//cout << "\tTRAVERSE " << u << endl;
int x = 0;
for (int v : al[u]) if (v != pa[u] && v != p) {
//cout << "\t\tNEI " << v << " :: " << w[v] << endl;
if (w[v]+(d[v]-d[u])+b > mid) ++x;
}
b += x;
if (b > i+1) bad = 1;
}

//cout << mid << " :: " << bad << endl;
(bad ? lo : hi) = mid;
}

cout << hi << '\n';
}
```

#### Subtask #1 0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #2 0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 479 ms 103700 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #3 0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #4 0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -