oj.uz

Submission #544148

# Submission time Handle Problem Language Result Execution time Memory
544148 2022-04-01T08:34:51 Z levladiator Pastiri (COI20_pastiri) C++14
100 / 100
 626 ms 64040 KB 
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define EPSILON 0.000001
#define CH (*s-'a')

using namespace std;

const ll NMAX = 5e5 + 5, INF = 1e18, MOD = 1e9 + 7, MMAX = 1e2 + 5, inf = 1e9;

ifstream fin("sufle.in");
ofstream fout("sufle.out");

int N,K;
int sheep[NMAX],dep[NMAX],dist[NMAX],anc[NMAX],v[NMAX];
bool vis[NMAX];
vector<int> adj[NMAX],ans;

bool cmp(int a,int b)
{
    return dep[a]>dep[b];
}

void bfs()
{
    queue<int> Q;
    for(int i=1;i<=N;i++)
    {
        if(sheep[i])Q.push(i);
    }
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        for(auto vec : adj[node])
        {
            if(!sheep[vec]&&!dist[vec])
            {
                dist[vec]=dist[node]+1;
                Q.push(vec);
            }
        }
    }
}

void dfs(int node,int prev,int last)
{
    dep[node]=dep[prev]+1;
    if(dist[last]+dep[last]<dist[node]+dep[node])
    {
        last=node;
    }
    anc[node]=last;
    for(auto son : adj[node])
    {
        if(son==prev)
            continue;

        dfs(son,node,last);
    }
}

void mark(int node)
{
    vis[node]=1;
    for(auto vec : adj[node])
    {
        if(vis[vec])
            continue;

        if(dist[vec]+1==dist[node])
        {
            mark(vec);
        }
    }
}

int main()
{
    cin.tie ( 0 )->sync_with_stdio ( 0 );
    cin.tie ( NULL );
    cout.tie ( NULL );

    cin>>N>>K;
    for(int i=1;i<N;i++)
    {
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i=1;i<=K;i++)
    {
        int x;
        cin>>x;
        sheep[x]=1;
    }
    bfs();
    dfs(1,0,0);
    int cnt=0;
    for(int i=1;i<=N;i++)
    {
        if(sheep[i])
        {
            v[++cnt]=i;
        }
    }
    sort(v+1,v+K+1,cmp);
    for(int i=1;i<=K;i++)
    {
        int node=v[i];
        if(!vis[node])
        {
            ans.pb(anc[node]);
            mark(anc[node]);
        }
    }
    cout<<ans.size()<<'\n';
    for(auto x : ans)
    {
        cout<<x<<' ';
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 57144 KB Output is correct
2 Correct 195 ms 58976 KB Output is correct
3 Correct 178 ms 59096 KB Output is correct
4 Correct 214 ms 64040 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 421 ms 34472 KB Output is correct
4 Correct 377 ms 36596 KB Output is correct
5 Correct 514 ms 34176 KB Output is correct
6 Correct 626 ms 36184 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12220 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 7 ms 12124 KB Output is correct
5 Correct 7 ms 12148 KB Output is correct
6 Correct 7 ms 12224 KB Output is correct
7 Correct 7 ms 12228 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 7 ms 12228 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12092 KB Output is correct
12 Correct 7 ms 12092 KB Output is correct
13 Correct 8 ms 12244 KB Output is correct
14 Correct 7 ms 12152 KB Output is correct
15 Correct 7 ms 12236 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 36832 KB Output is correct
2 Correct 479 ms 36644 KB Output is correct
3 Correct 497 ms 46532 KB Output is correct
4 Correct 520 ms 42668 KB Output is correct
5 Correct 370 ms 41028 KB Output is correct
6 Correct 534 ms 50204 KB Output is correct
7 Correct 532 ms 48832 KB Output is correct
8 Correct 532 ms 48560 KB Output is correct
9 Correct 607 ms 42556 KB Output is correct
10 Correct 512 ms 40860 KB Output is correct
11 Correct 348 ms 44840 KB Output is correct
12 Correct 305 ms 48028 KB Output is correct
13 Correct 353 ms 50180 KB Output is correct
14 Correct 289 ms 45984 KB Output is correct
15 Correct 46 ms 17264 KB Output is correct
16 Correct 560 ms 40676 KB Output is correct
17 Correct 339 ms 41352 KB Output is correct
18 Correct 479 ms 37088 KB Output is correct
19 Correct 507 ms 47580 KB Output is correct
20 Correct 519 ms 50032 KB Output is correct
21 Correct 470 ms 42584 KB Output is correct
22 Correct 465 ms 43060 KB Output is correct