oj.uz

Submission #877244

# Submission time Handle Problem Language Result Execution time Memory
877244 2023-11-23T04:48:33 Z bachhoangxuan Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 73408 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e9;
const int mod=998244353;
const int maxn=500005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=20;
const int maxa=1000000;
const int root=3;
const int base=101;

int n,k,c[maxn],d[maxn],dep[maxn],par[maxn];
bool del[maxn];
vector<int> edge[maxn];
vector<int> sheep;

void dfs(int u,int p){
    dep[u]=dep[p]+1;par[u]=p;
    if(c[u]) sheep.push_back(u);
    for(int v:edge[u]) if(v!=p) dfs(v,u);
}

void bfs(int u,int p,int D){
    del[u]=true;
    if(D==0) return;
    for(int v:edge[u]) if(d[v]<d[u]) bfs(v,u,D-1);
}

void solve(){
    cin >> n >> k;
    for(int i=1;i<n;i++){
        int u,v;cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=k;i++){
        int x;cin >> x;
        c[x]=1;
    }
    dfs(1,0);
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(c[i]) d[i]=0,q.push(i);
        else d[i]=-1;
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v:edge[u]){
            if(d[v]==-1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    sort(sheep.begin(),sheep.end(),[=](int x,int y){return dep[x]>dep[y];});
    vector<int> ans;
    for(int x:sheep){
        if(del[x]) continue;
        int u=x;
        while(par[u] && d[par[u]]==dep[x]-dep[par[u]]) u=par[u];
        ans.push_back(u);
        bfs(u,0,d[u]);
    }
    cout << (int)ans.size() << '\n';
    for(int v:ans) cout << v << ' ';
    cout << '\n';
}

signed main(){
    //freopen("SHEEP.INP","r",stdin);
    //freopen("SHEEP.OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 64864 KB Output is correct
2 Correct 136 ms 65872 KB Output is correct
3 Correct 139 ms 65876 KB Output is correct
4 Correct 169 ms 73408 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17244 KB Output is correct
2 Correct 4 ms 17244 KB Output is correct
3 Correct 260 ms 41852 KB Output is correct
4 Correct 248 ms 44372 KB Output is correct
5 Correct 336 ms 41296 KB Output is correct
6 Correct 790 ms 43548 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 17068 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 4 ms 16988 KB Output is correct
12 Correct 3 ms 17012 KB Output is correct
13 Correct 4 ms 17060 KB Output is correct
14 Correct 4 ms 17240 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 43600 KB Output is correct
2 Correct 328 ms 43552 KB Output is correct
3 Correct 358 ms 46960 KB Output is correct
4 Correct 344 ms 42788 KB Output is correct
5 Correct 232 ms 41768 KB Output is correct
6 Correct 447 ms 50884 KB Output is correct
7 Correct 361 ms 49348 KB Output is correct
8 Correct 384 ms 48840 KB Output is correct
9 Correct 486 ms 42580 KB Output is correct
10 Correct 387 ms 41300 KB Output is correct
11 Correct 236 ms 44628 KB Output is correct
12 Correct 217 ms 48676 KB Output is correct
13 Correct 249 ms 50604 KB Output is correct
14 Correct 193 ms 46420 KB Output is correct
15 Correct 36 ms 21460 KB Output is correct
16 Execution timed out 1076 ms 40784 KB Time limit exceeded
17 Halted 0 ms 0 KB -