# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
209241 | DodgeBallMan | Cat in a tree (BOI17_catinatree) | C++14 | 269 ms | 32120 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
int n, t, d, dep[N], sz[N], st[N], en[N], hv[N];
vector<int> g[N];
multiset<int> s;
void dfs( int u, int p ) {
st[u] = ++t, sz[u] = 1, dep[u] = dep[p] + 1;
pii ret( -1e9, -1 );
for( int v : g[u] ) if( v != p ) {
dfs( v, u );
sz[u] += sz[v];
ret = max( ret, pii( sz[v], v ) );
}
hv[u] = ret.y, en[u] = t;
}
void sack( multiset<int> &s, int u, int p ) {
if( hv[u] != -1 ) sack( s, hv[u], u );
multiset<int> t;
for( int v : g[u] ) if( v != p && v != hv[u] ) {
sack( t, v, u );
while( !s.empty() && !t.empty() && *s.begin() + *t.begin() - 2*dep[u] < d ) {
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |