Submission #1166385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166385		son2008	Pastiri (COI20_pastiri)	C++20	100 / 100	416 ms	71808 KiB

pastiri

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e5+1;
const int mod=1e9+7;
int n,dist[maxn],h[maxn],vis[maxn],k,o[maxn],par[maxn];
vector<int>a[maxn];
void pre(int u,int cha)
{
    for(int v:a[u])
    {
        if(v==cha)continue;
        par[v]=u;
        h[v]=h[u]+1;
        pre(v,u);
    }
}
void init()
{
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for(int i=1;i<=k;i++)
    {
        cin>>o[i];
    }
}
bool cmp(int x,int y)
{
    return h[x]>h[y];
}
void dfs(int u,int s)
{
    vis[u]=1;
    for(int v:a[u])
    {
        if(vis[v]||dist[v]!=s-1)continue;
        dfs(v,s-1);
    }
}
void process()
{
    pre(1,-1);
    queue<int>q;
    memset(dist,0x3f,sizeof(dist));
    for(int i=1;i<=k;i++)
    {
        dist[o[i]]=0;
        q.push(o[i]);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int v:a[u])
        {
            if(dist[v]>dist[u]+1)
            {
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
    sort(o+1,o+k+1,cmp);
    vector<int>ans;
    for(int i=1;i<=k;i++)
    {
        if(vis[o[i]])continue;
        int u=o[i];
        while(par[u]&&dist[par[u]]==dist[u]+1)u=par[u];
      //  cout<<o[i]<<" "<<u<<'\n';
        ans.push_back(u);
        dfs(u,h[o[i]]-h[u]);
    }
    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());
    for(int x:ans)cout<<x<<" ";
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51