oj.uz

Submission #986340

# Submission time Handle Problem Language Result Execution time Memory
986340 2024-05-20T10:52:42 Z alexdd Pastiri (COI20_pastiri) C++17
100 / 100
 611 ms 164744 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];
bool isoaie[500005];
vector<int> sol;
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 x, int d)
{
    dfs_sterge(x,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];
}
set<int> s[500005];
bool gata[500005];
void dfs2(int nod, int par)
{
    sort(con[nod].begin(),con[nod].end(),cmp);
    bool rau=0;
    for(auto adj:con[nod])
    {
        if(adj==par || mind[adj]==INF)
            continue;

        dfs2(adj,nod);
        if(s[nod].find(2*depth[nod]-mind[nod])!=s[nod].end())
            gata[adj]=1;

        if((int)s[adj].size() > (int)s[nod].size())
            swap(s[adj],s[nod]);
        for(auto x:s[adj])
            s[nod].insert(x);

        if(gata[adj])
            continue;

        if(mind[adj]!=mind[nod] || mind[nod]-depth[nod] > closest[nod])
        {
            sol.push_back(adj);
            ///sterge(adj,closest[adj]);
            s[nod].insert(depth[adj]-closest[adj]);
            gata[adj]=1;
        }
        else
            rau=1;
    }
    if(mind[nod]==INF)
    {
        gata[nod]=1;
        return;
    }
    if(closest[nod]==0 && s[nod].find(2*depth[nod]-mind[nod])!=s[nod].end())
    {
        gata[nod]=1;
        return;
    }
    if(mind[nod]-depth[nod] > closest[nod])
    {
        gata[nod]=1;
        return;
    }
    if(closest[nod]==0)
        rau=1;
    if(!rau)
    {
        gata[nod]=1;
        return;
    }
    if(mind[nod]-depth[nod]==closest[nod] && (nod==1 || mind[nod]-depth[par]!=closest[par]))
    {
        //cout<<nod<<" sters nod\n";
        sol.push_back(nod);
        ///sterge(nod,closest[nod]);
        s[nod].insert(depth[nod]-closest[nod]);
        gata[nod]=1;
    }
}
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;
}
/**

depth[x] - closest[x] = 2*depth[nod] - mind[nod]

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 102844 KB Output is correct
2 Correct 216 ms 149844 KB Output is correct
3 Correct 217 ms 149840 KB Output is correct
4 Correct 320 ms 164744 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 42276 KB Output is correct
2 Correct 10 ms 42076 KB Output is correct
3 Correct 320 ms 67304 KB Output is correct
4 Correct 315 ms 72240 KB Output is correct
5 Correct 410 ms 64304 KB Output is correct
6 Correct 584 ms 71868 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 42076 KB Output is correct
2 Correct 11 ms 42164 KB Output is correct
3 Correct 11 ms 42076 KB Output is correct
4 Correct 11 ms 42076 KB Output is correct
5 Correct 9 ms 42076 KB Output is correct
6 Correct 10 ms 42076 KB Output is correct
7 Correct 10 ms 42076 KB Output is correct
8 Correct 9 ms 42076 KB Output is correct
9 Correct 10 ms 42076 KB Output is correct
10 Correct 9 ms 42076 KB Output is correct
11 Correct 9 ms 42076 KB Output is correct
12 Correct 9 ms 42076 KB Output is correct
13 Correct 10 ms 42076 KB Output is correct
14 Correct 9 ms 42076 KB Output is correct
15 Correct 10 ms 42076 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 69284 KB Output is correct
2 Correct 468 ms 68652 KB Output is correct
3 Correct 535 ms 73288 KB Output is correct
4 Correct 611 ms 64380 KB Output is correct
5 Correct 420 ms 67804 KB Output is correct
6 Correct 547 ms 78444 KB Output is correct
7 Correct 555 ms 77600 KB Output is correct
8 Correct 548 ms 77816 KB Output is correct
9 Correct 584 ms 64700 KB Output is correct
10 Correct 456 ms 67700 KB Output is correct
11 Correct 321 ms 73536 KB Output is correct
12 Correct 362 ms 75304 KB Output is correct
13 Correct 352 ms 77432 KB Output is correct
14 Correct 288 ms 74332 KB Output is correct
15 Correct 46 ms 50004 KB Output is correct
16 Correct 533 ms 66956 KB Output is correct
17 Correct 362 ms 72248 KB Output is correct
18 Correct 445 ms 64592 KB Output is correct
19 Correct 510 ms 84808 KB Output is correct
20 Correct 546 ms 95400 KB Output is correct
21 Correct 396 ms 70196 KB Output is correct
22 Correct 417 ms 71548 KB Output is correct