Submission #833995

#	Time	Username	Problem	Language	Result	Execution time	Memory
833995		vjudge1	Pastiri (COI20_pastiri)	C++17	0 / 100	1075 ms	72024 KiB

pastiri

#include <bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define pb push_back
using namespace std;
const int maxn=5e5+9;
vector<int>a[maxn];
int b[maxn];
int n,k;
int d[maxn];
bool vis[maxn];
int dep[2009][2009];
int cnt[2009];
bool hav[2009][2009];
void dfs(int u,int par,int root){
for (auto v:a[u]){
    if (v==par)continue;
    dep[root][v]=dep[root][u]+1;
    dfs(v,u,root);
}
}
void sp(){
    queue<int>c;
    for1(i,1,k){
    d[b[i]]=0;
    vis[b[i]]=1;
    c.push(b[i]);
    }
    while (!c.empty()){
        auto u=c.front();
        c.pop();
        vis[u]=1;
        for (auto v:a[u]){
            if (!vis[v]){
                vis[v]=1;
                d[v]=d[u]+1;
                c.push(v);
            }
        }
    }
}
void sol()
{
    cin>>n>>k;
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    for1(i,1,k)cin>>b[i];
    sp();
    for1(i,1,n)dfs(i,0,i);
    for1(i,1,k){
    for1(j,1,n){
    if (dep[b[i]][j]==d[j]){
        cnt[j]++;
        hav[j][b[i]]=1;
    }
    }
    }
    int num=0;
   vector<int>take;
    while (true){
        int mx=0;
        for1(i,1,n)mx=max(mx,cnt[i]);
        if (mx==0)break;
        for1(i,1,n){
        if (mx==cnt[i]){
            num++;
            take.pb(i);
            for1(j,1,k){
            if (hav[i][b[j]]){
                for1(l,1,n){
                if (hav[l][b[j]]){
                    hav[l][b[j]]=0;
                    cnt[l]--;
                }
                }
            }
            }
            break;
        }
        }
    }
    cout<<num<<'\n';
  for (auto v:take)cout<<v<<" ";

}
signed main()
{
    //freopen("WHARF.INP", "r", stdin);
    //freopen("WHARF.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    sol();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51