oj.uz

Submission #544227

# Submission time Handle Problem Language Result Execution time Memory
544227 2022-04-01T12:37:12 Z robertbarbu27 Pastiri (COI20_pastiri) C++14
92 / 100
 670 ms 164912 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[500005];
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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 164912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24020 KB Output is correct
2 Correct 13 ms 24068 KB Output is correct
3 Correct 412 ms 48868 KB Output is correct
4 Correct 400 ms 51088 KB Output is correct
5 Correct 545 ms 48496 KB Output is correct
6 Correct 670 ms 52836 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 12 ms 23848 KB Output is correct
3 Correct 13 ms 24036 KB Output is correct
4 Correct 12 ms 23852 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 24020 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 12 ms 23900 KB Output is correct
10 Correct 14 ms 23844 KB Output is correct
11 Correct 13 ms 23892 KB Output is correct
12 Correct 12 ms 23848 KB Output is correct
13 Correct 13 ms 23980 KB Output is correct
14 Correct 14 ms 24020 KB Output is correct
15 Correct 13 ms 23944 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 52100 KB Output is correct
2 Correct 510 ms 51816 KB Output is correct
3 Correct 597 ms 54208 KB Output is correct
4 Correct 544 ms 51056 KB Output is correct
5 Correct 413 ms 49916 KB Output is correct
6 Correct 576 ms 58812 KB Output is correct
7 Correct 586 ms 57104 KB Output is correct
8 Correct 580 ms 56812 KB Output is correct
9 Correct 638 ms 53208 KB Output is correct
10 Correct 536 ms 49164 KB Output is correct
11 Correct 382 ms 53068 KB Output is correct
12 Correct 334 ms 55540 KB Output is correct
13 Correct 388 ms 56876 KB Output is correct
14 Correct 303 ms 54704 KB Output is correct
15 Correct 53 ms 28748 KB Output is correct
16 Correct 580 ms 49448 KB Output is correct
17 Correct 385 ms 50240 KB Output is correct
18 Correct 519 ms 46976 KB Output is correct
19 Correct 539 ms 58872 KB Output is correct
20 Correct 585 ms 65220 KB Output is correct
21 Correct 482 ms 51260 KB Output is correct
22 Correct 512 ms 52104 KB Output is correct