oj.uz

Submission #986323

# Submission time Handle Problem Language Result Execution time Memory
986323 2024-05-20T10:13:08 Z alexdd Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 108916 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
int n,k;
vector<int> con[500005];
int closest[500005];
int mind[500005];
int depth[500005];
int cnt[500005];
bool isoaie[500005];
vector<int> sol;
int init;
void dfs_sterge(int nod, int par, int d)
{
    if(d==0)
    {
        isoaie[nod]=0;
        return;
    }
    for(auto adj:con[nod])
        if(adj!=par)
            dfs_sterge(adj,nod,d-1);
}
void sterge(int nod, int d)
{
    init=nod;
    dfs_sterge(nod,0,d);
}
void dfs(int nod, int par)
{
    mind[nod]=INF;
    if(closest[nod]==0) mind[nod]=depth[nod];
    for(auto adj:con[nod])
    {
        if(adj==par)
            continue;
        depth[adj]=depth[nod]+1;
        dfs(adj,nod);
        mind[nod] = min(mind[nod], mind[adj]);
    }
}
bool cmp(int x, int y)
{
    return mind[x] > mind[y];
}
void dfs2(int nod, int par)
{
    cnt[nod]=0;
    sort(con[nod].begin(),con[nod].end(),cmp);
    for(auto adj:con[nod])
    {
        if(adj==par)
            continue;
        dfs2(adj,nod);
        if(cnt[adj]==0)
            continue;
        if(mind[adj]!=mind[nod] || mind[nod]-depth[nod] > closest[nod])
        {
            sol.push_back(adj);
            sterge(adj,closest[adj]);
            cnt[adj]=0;
        }
        else
            cnt[nod] += cnt[adj];
    }
    if(isoaie[nod]) cnt[nod]++;
    if(cnt[nod]==0)
        return;
    if(mind[nod]-depth[nod]==closest[nod] && (nod==1 || mind[nod]-depth[par]!=closest[par]))
    {
        sol.push_back(nod);
        sterge(nod,closest[nod]);
        cnt[nod]=0;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        con[u].push_back(v);
        con[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        closest[i]=INF;
    deque<int> dq;
    for(int i=1;i<=k;i++)
    {
        cin>>u;
        isoaie[u]=1;
        closest[u]=0;
        dq.push_back(u);
    }
    while(!dq.empty())
    {
        int nod = dq.front();
        dq.pop_front();
        for(auto adj:con[nod])
        {
            if(closest[adj] > closest[nod]+1)
            {
                closest[adj] = closest[nod]+1;
                dq.push_back(adj);
            }
        }
    }
    depth[1]=1;
    dfs(1,0);
    dfs2(1,0);
    cout<<sol.size()<<"\n";
    for(auto x:sol)
        cout<<x<<" ";
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 102140 KB Output is correct
2 Correct 186 ms 102292 KB Output is correct
3 Correct 191 ms 102364 KB Output is correct
4 Correct 230 ms 108916 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22104 KB Output is correct
2 Correct 7 ms 22108 KB Output is correct
3 Correct 422 ms 51100 KB Output is correct
4 Correct 435 ms 55920 KB Output is correct
5 Correct 604 ms 47728 KB Output is correct
6 Execution timed out 1035 ms 52264 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22108 KB Output is correct
2 Correct 5 ms 22108 KB Output is correct
3 Correct 5 ms 22108 KB Output is correct
4 Correct 5 ms 21852 KB Output is correct
5 Correct 5 ms 21948 KB Output is correct
6 Correct 5 ms 22104 KB Output is correct
7 Correct 5 ms 21852 KB Output is correct
8 Correct 5 ms 22108 KB Output is correct
9 Correct 5 ms 22108 KB Output is correct
10 Correct 5 ms 22104 KB Output is correct
11 Correct 5 ms 21848 KB Output is correct
12 Correct 5 ms 22080 KB Output is correct
13 Correct 5 ms 22104 KB Output is correct
14 Correct 5 ms 22108 KB Output is correct
15 Correct 5 ms 22108 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 51600 KB Output is correct
2 Correct 496 ms 51392 KB Output is correct
3 Correct 495 ms 53980 KB Output is correct
4 Correct 544 ms 47476 KB Output is correct
5 Correct 380 ms 48756 KB Output is correct
6 Correct 466 ms 60432 KB Output is correct
7 Correct 530 ms 57416 KB Output is correct
8 Correct 479 ms 56452 KB Output is correct
9 Execution timed out 1004 ms 47644 KB Time limit exceeded
10 Halted 0 ms 0 KB -