oj.uz

Submission #593494

# Submission time Handle Problem Language Result Execution time Memory
593494 2022-07-11T09:19:59 Z jiahng Pastiri (COI20_pastiri) C++14
100 / 100
 843 ms 194264 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,ll> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 500100
#define INF (ll)1e14
#define MOD 1000000007
#define getchar_unlocked _getchar_nolock
int N,K,a,b;
vi adj[maxn];
int dist[maxn];
int depth[maxn], twok[maxn][30];
bool covered[maxn];
void dfs(int x, int p){
    twok[x][0] = p;
    FOR(i,1,29){
        if (twok[x][i-1] == -1) break;
        twok[x][i] = twok[twok[x][i-1]][i-1];
    }
    aFOR(i,adj[x]) if (i != p){
        depth[i] = depth[x] + 1;
        dfs(i,x);
    }
}
void dfs2(int x){
    covered[x] = 1;
    aFOR(i,adj[x]) if (!covered[i] && dist[i] + 1 == dist[x]) dfs2(i);
}
int32_t main(){
    fast;
    cin >> N >> K;
    FOR(i,1,N-1){
        cin >> a >> b; adj[a].pb(b); adj[b].pb(a);
    }
    vi sheep;
    FOR(i,1,K){
        cin >> a; sheep.pb(a);
    }
    queue <int> q;
    mem(dist, -1);
    aFOR(i,sheep){
       q.push(i);
       dist[i] = 0;
    }
    while (!q.empty()){
        int cur = q.front(); q.pop();
        aFOR(i,adj[cur]){
            if (dist[i] != -1) continue;
            dist[i] = dist[cur] + 1;
            q.push(i);
        }
    }
    //FOR(i,1,N) cout << dist[i] << ' ';
    //cout << '\n';
    mem(twok, -1);
    dfs(1,-1);
    sort(all(sheep), [](int i,int j){
        return depth[i] > depth[j];
    });
    vi ans;
    aFOR(i,sheep) if (!covered[i]){
        int x = i;
        DEC(k,29,0){
            if (twok[x][k] != -1 && dist[twok[x][k]] == depth[i] - depth[twok[x][k]]) x = twok[x][k];
        }
        ans.pb(x);
        dfs2(x);
    }
    cout << ans.size() << '\n';
    aFOR(i, ans) cout << i << ' ';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 183128 KB Output is correct
2 Correct 395 ms 183580 KB Output is correct
3 Correct 344 ms 183528 KB Output is correct
4 Correct 464 ms 194264 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 133632 KB Output is correct
2 Correct 57 ms 133684 KB Output is correct
3 Correct 445 ms 163472 KB Output is correct
4 Correct 477 ms 168400 KB Output is correct
5 Correct 604 ms 160200 KB Output is correct
6 Correct 832 ms 162132 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 133496 KB Output is correct
2 Correct 55 ms 133424 KB Output is correct
3 Correct 60 ms 133548 KB Output is correct
4 Correct 49 ms 133424 KB Output is correct
5 Correct 52 ms 133568 KB Output is correct
6 Correct 52 ms 133456 KB Output is correct
7 Correct 58 ms 133400 KB Output is correct
8 Correct 57 ms 133456 KB Output is correct
9 Correct 55 ms 133580 KB Output is correct
10 Correct 51 ms 133556 KB Output is correct
11 Correct 54 ms 133436 KB Output is correct
12 Correct 50 ms 133404 KB Output is correct
13 Correct 51 ms 133468 KB Output is correct
14 Correct 57 ms 133556 KB Output is correct
15 Correct 62 ms 133516 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 163632 KB Output is correct
2 Correct 570 ms 163520 KB Output is correct
3 Correct 668 ms 169248 KB Output is correct
4 Correct 593 ms 160144 KB Output is correct
5 Correct 508 ms 161564 KB Output is correct
6 Correct 753 ms 173392 KB Output is correct
7 Correct 843 ms 170688 KB Output is correct
8 Correct 802 ms 169612 KB Output is correct
9 Correct 750 ms 160172 KB Output is correct
10 Correct 588 ms 160168 KB Output is correct
11 Correct 441 ms 166204 KB Output is correct
12 Correct 458 ms 170704 KB Output is correct
13 Correct 426 ms 173716 KB Output is correct
14 Correct 427 ms 166928 KB Output is correct
15 Correct 106 ms 138384 KB Output is correct
16 Correct 654 ms 158640 KB Output is correct
17 Correct 487 ms 162384 KB Output is correct
18 Correct 561 ms 155464 KB Output is correct
19 Correct 684 ms 168200 KB Output is correct
20 Correct 788 ms 170428 KB Output is correct
21 Correct 513 ms 162648 KB Output is correct
22 Correct 537 ms 163076 KB Output is correct