oj.uz

Submission #447281

# Submission time Handle Problem Language Result Execution time Memory
447281 2021-07-25T18:50:52 Z MOUF_MAHMALAT Pastiri (COI20_pastiri) C++11
100 / 100
 821 ms 45592 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
ll n,x,y,k,d[500009],a[500009],h[500009],c;
pll op[500009];
vector<vector<ll> >v;
queue<ll>q;
vector<ll>ans;
bool b[500009];
bool cmp(const ll&xo,const ll&yo)
{
    return h[xo]>h[yo];
}
struct node
{
    ll f,s,t;
};
queue<node>dq;
int main()
{
    scanf("%d%d",&n,&k);
    v.resize(n+1);
    for(ll i=1; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(ll i=1; i<=n; i++)
        d[i]=h[i]=1e9,op[i]= {1e9,1e9};
    h[1]=1;
    q.push(1);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(auto z:v[x])
            if(h[z]>h[x]+1)
            {
                h[z]=h[x]+1;
                q.push(z);
            }
    }
    for(ll i=1; i<=k; i++)
        scanf("%d",&a[i]),d[a[i]]=0,q.push(a[i]);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(auto z:v[x])
        {
            if(d[z]<=d[x]+1)
                continue;
            d[z]=d[x]+1;
            q.push(z);
        }
    }
    dq.push({1,0,1});
    while(!dq.empty())
    {
        x=dq.front().f;
        ll p=dq.front().s;
        ll id=dq.front().t;
        dq.pop();
        if(d[x]==0)
            op[x]= {h[id],id};
        for(auto z:v[x])
        {
            if(z==p)
                continue;
            if(d[x]==d[z]+1)
                dq.push({z,x,id});
            else
                dq.push({z,x,z});
        }
    }
    sort(a+1,a+k+1,cmp);
    for(ll i=1; i<=k; i++)
    {
        if(b[a[i]])
            continue;
        ans.push_back(op[a[i]].second);
        q.push(op[a[i]].second);
        while(!q.empty())
        {
            x=q.front();
            q.pop();
            b[x]=1;
            for(auto z:v[x])
                if(d[x]==d[z]+1&&b[z]==0)
                    q.push(z);
        }
    }
    x=ans.size();
    printf("%d\n",x);
    for(auto z:ans)
        printf("%d ",z);
    return 0;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
pastiri.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
pastiri.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d",&a[i]),d[a[i]]=0,q.push(a[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 35908 KB Output is correct
2 Correct 255 ms 36292 KB Output is correct
3 Correct 260 ms 36252 KB Output is correct
4 Correct 371 ms 41096 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 566 ms 38196 KB Output is correct
4 Correct 550 ms 41724 KB Output is correct
5 Correct 714 ms 36220 KB Output is correct
6 Correct 771 ms 36312 KB Output is correct

Subtask #3
23.0 / 23.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 36808 KB Output is correct
2 Correct 640 ms 36724 KB Output is correct
3 Correct 769 ms 39280 KB Output is correct
4 Correct 698 ms 36368 KB Output is correct
5 Correct 561 ms 32700 KB Output is correct
6 Correct 752 ms 40156 KB Output is correct
7 Correct 767 ms 40084 KB Output is correct
8 Correct 776 ms 39748 KB Output is correct
9 Correct 821 ms 36288 KB Output is correct
10 Correct 694 ms 36184 KB Output is correct
11 Correct 514 ms 40528 KB Output is correct
12 Correct 494 ms 45592 KB Output is correct
13 Correct 564 ms 45096 KB Output is correct
14 Correct 446 ms 42972 KB Output is correct
15 Correct 67 ms 6716 KB Output is correct
16 Correct 705 ms 33784 KB Output is correct
17 Correct 526 ms 40328 KB Output is correct
18 Correct 597 ms 35036 KB Output is correct
19 Correct 689 ms 44348 KB Output is correct
20 Correct 730 ms 43472 KB Output is correct
21 Correct 627 ms 42856 KB Output is correct
22 Correct 632 ms 42764 KB Output is correct