oj.uz

Submission #544230

# Submission time Handle Problem Language Result Execution time Memory
544230 2022-04-01T12:45:38 Z robertbarbu27 Pastiri (COI20_pastiri) C++14
100 / 100
 700 ms 116776 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
ifstream f("teroristi2.in");
ofstream g("teroristi2.out");
vector<int> adj[500005];
int N,K;
int sheep[500005],dist[500005],lvl[500005];
int best[500005];
queue<int> Q;
vector<int> v[1000005];
bool OK[500005];
vector<int> ans;
bool viz[500005];
void dfs_best(int node,int dad)
{
    lvl[node]=lvl[dad]+1;
    v[dist[node]+lvl[node]].push_back(node);
    if(OK[node]==1)
    {
        best[node]=v[dist[node]+lvl[node]].front();
    }
    for(auto x:adj[node])
    {
        if(x!=dad)
        {
            dfs_best(x,node);
        }
    }
    v[dist[node]+lvl[node]].pop_back();

}
bool cmp(int a,int b)
{
    return lvl[a]>lvl[b];
}
void removenodes(int node)
{
    viz[node]=1;
    for(auto x:adj[node])
    {
        if(dist[x]+1==dist[node]&&viz[x]==0)
        {
            removenodes(x);
        }
    }

}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>K;
    for(int i=1; i<=N; i++) dist[i]=1e9;
    for(int i=1; i<N; i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1; i<=K; i++)
    {
        cin>>sheep[i];
        Q.push(sheep[i]);
        dist[sheep[i]]=0;
        OK[sheep[i]]=1;
    }
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        for(auto x:adj[node])
        {
            if(dist[x]>dist[node]+1)
            {
                dist[x]=dist[node]+1;
                Q.push(x);
            }
        }
    }
    dfs_best(1,0);
    sort(sheep+1,sheep+K+1,cmp);
    for(int i=1; i<=K; i++)
    {
       // cout<<best[sheep[i]]<<" ";
        if(viz[sheep[i]]==0)
        {
            removenodes(best[sheep[i]]);
            ans.pb(best[sheep[i]]);
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<'\n';
    for(auto x:ans) cout<<x<<" ";






}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 107656 KB Output is correct
2 Correct 210 ms 110616 KB Output is correct
3 Correct 227 ms 110612 KB Output is correct
4 Correct 313 ms 116776 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35796 KB Output is correct
2 Correct 19 ms 35812 KB Output is correct
3 Correct 417 ms 56376 KB Output is correct
4 Correct 420 ms 58640 KB Output is correct
5 Correct 541 ms 56156 KB Output is correct
6 Correct 700 ms 60328 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35588 KB Output is correct
2 Correct 22 ms 35796 KB Output is correct
3 Correct 19 ms 35656 KB Output is correct
4 Correct 19 ms 35672 KB Output is correct
5 Correct 17 ms 35660 KB Output is correct
6 Correct 21 ms 35716 KB Output is correct
7 Correct 20 ms 35668 KB Output is correct
8 Correct 19 ms 35668 KB Output is correct
9 Correct 19 ms 35668 KB Output is correct
10 Correct 19 ms 35716 KB Output is correct
11 Correct 19 ms 35564 KB Output is correct
12 Correct 18 ms 35668 KB Output is correct
13 Correct 19 ms 35668 KB Output is correct
14 Correct 19 ms 35796 KB Output is correct
15 Correct 20 ms 35668 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 59648 KB Output is correct
2 Correct 503 ms 59444 KB Output is correct
3 Correct 560 ms 61516 KB Output is correct
4 Correct 526 ms 58424 KB Output is correct
5 Correct 410 ms 57024 KB Output is correct
6 Correct 563 ms 66068 KB Output is correct
7 Correct 585 ms 64328 KB Output is correct
8 Correct 588 ms 64056 KB Output is correct
9 Correct 649 ms 60556 KB Output is correct
10 Correct 557 ms 56428 KB Output is correct
11 Correct 385 ms 60236 KB Output is correct
12 Correct 335 ms 62780 KB Output is correct
13 Correct 387 ms 64076 KB Output is correct
14 Correct 322 ms 61844 KB Output is correct
15 Correct 61 ms 39628 KB Output is correct
16 Correct 591 ms 56776 KB Output is correct
17 Correct 395 ms 57276 KB Output is correct
18 Correct 538 ms 54256 KB Output is correct
19 Correct 528 ms 65732 KB Output is correct
20 Correct 561 ms 72304 KB Output is correct
21 Correct 487 ms 58184 KB Output is correct
22 Correct 503 ms 59184 KB Output is correct