oj.uz

Submission #447280

# Submission time Handle Problem Language Result Execution time Memory
447280 2021-07-25T18:48:15 Z MOUF_MAHMALAT Pastiri (COI20_pastiri) C++11
49 / 100
 1000 ms 53412 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};
    //for dfs
    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]);
    //for each node what is the dis to the closest sheep
    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);
        }
    }
    //
    // for each sheep what is th highest par can be reached
    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});
        }
    }
    //
    // starting for the deepest sheep
    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)
                    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:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         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 204 ms 39692 KB Output is correct
2 Correct 245 ms 40084 KB Output is correct
3 Correct 255 ms 40156 KB Output is correct
4 Correct 369 ms 44924 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 561 ms 41860 KB Output is correct
4 Correct 536 ms 45356 KB Output is correct
5 Correct 684 ms 40008 KB Output is correct
6 Correct 854 ms 40044 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 4 ms 460 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 40480 KB Output is correct
2 Correct 628 ms 40444 KB Output is correct
3 Correct 704 ms 43204 KB Output is correct
4 Correct 695 ms 40116 KB Output is correct
5 Correct 550 ms 36488 KB Output is correct
6 Correct 725 ms 44544 KB Output is correct
7 Correct 773 ms 43852 KB Output is correct
8 Correct 759 ms 43692 KB Output is correct
9 Correct 782 ms 40132 KB Output is correct
10 Correct 682 ms 42520 KB Output is correct
11 Correct 492 ms 46892 KB Output is correct
12 Correct 482 ms 53224 KB Output is correct
13 Correct 561 ms 53412 KB Output is correct
14 Correct 421 ms 49432 KB Output is correct
15 Correct 57 ms 7492 KB Output is correct
16 Execution timed out 1085 ms 39564 KB Time limit exceeded
17 Halted 0 ms 0 KB -