Submission #593494

#	Time	Username	Problem	Language	Result	Execution time	Memory
593494		jiahng	Pastiri (COI20_pastiri)	C++14	100 / 100	843 ms	194264 KiB

pastiri

#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 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51