oj.uz

Submission #701079

# Submission time Handle Problem Language Result Execution time Memory
701079 2023-02-20T03:34:01 Z aSSSd Pastiri (COI20_pastiri) C++14
100 / 100
 847 ms 145740 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r)
{
    return l+rng()%(r-l+1);
}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define forinc(x,a,b) for(int x=a;x<=b;x++)
#define fordec(x,a,b) for(int x=a;x>=b;x--)
#define fi first
#define se second
#define ii pair<int,int>
#define getbit(x,i) ((x>>(i))&1ll)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1ll<<(i)))
#define endl '\n'
//#define int long long
#define pb push_back
const int N = 5e5+10;
int n, k;
int a[N], l[N];
vector<int> ke[N];
vector<int> adj[N];
int P[N][20];
void dfs(int u, int pr)
{
    forinc( i, 1,18 )   P[u][i] = P[P[u][i-1]][i-1];
    for(auto v : ke[u])
    {
        if(v==pr) continue;
        l[v] = l[u] + 1;
        P[v][0] = u;
        dfs(v,u);
    }
}
int d[N];
queue<int> q;
void bfs()
{
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto v : ke[u])
        {
            if(d[v] == -1)
            {
                d[v] = d[u] + 1;
                q.push(v);
            }
            if(d[v] == d[u] + 1)
            {
                adj[v].pb(u);
            }
        }
    }
}
bool cmp(int x, int y)
{
    return l[x] > l[y];
}
int dd[N];
main()
{
   // freopen("task.inp" , "r" , stdin);
    fasty;
    cin >> n >> k;
    forinc(i,1,n-1)
    {
        int a,b;
        cin >> a >> b;
        ke[a].pb(b);
        ke[b].pb(a);
    }
    dfs(1,0);
    forinc(i,1,n) d[i]=-1;
    forinc(i,1,k)
    {
        cin >> a[i];
        d[a[i]]=0;
        q.push(a[i]);
    }
    bfs();
    sort(a+1, a+k + 1, cmp);
    while(!q.empty()) q.pop();
    vector<int> ans;
    forinc(i,1,k)
    {
        if(dd[a[i]] ) continue;
        int cur=a[i];
        fordec(j,17,0)
        {
            int nxt = P[cur][j];
            if(!nxt) continue;
            if(l[a[i]] - l[nxt] <= d[nxt]) cur = nxt;
        }
        if(!dd[cur])
        {
            ans.pb(cur);
            dd[cur]=1;
            q.push(cur);
            while(!q.empty())
            {
                int u = q.front();
                q.pop();
                for(auto v : adj[u])
                {
                    if(!dd[v])
                    {
                        dd[v]=1;
                        q.push(v);
                    }
                }
            }
        }
    }
    cout << ans.size() << "\n";
    for(auto x : ans) cout << x << " ";
}

Compilation message

pastiri.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main()
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 144248 KB Output is correct
2 Correct 337 ms 145740 KB Output is correct
3 Correct 334 ms 145616 KB Output is correct
4 Correct 411 ms 142340 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24652 KB Output is correct
2 Correct 13 ms 24624 KB Output is correct
3 Correct 603 ms 105768 KB Output is correct
4 Correct 622 ms 107684 KB Output is correct
5 Correct 735 ms 106728 KB Output is correct
6 Correct 810 ms 110344 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24104 KB Output is correct
2 Correct 13 ms 24112 KB Output is correct
3 Correct 13 ms 24172 KB Output is correct
4 Correct 14 ms 24112 KB Output is correct
5 Correct 16 ms 24080 KB Output is correct
6 Correct 12 ms 24100 KB Output is correct
7 Correct 13 ms 24104 KB Output is correct
8 Correct 14 ms 24212 KB Output is correct
9 Correct 12 ms 24148 KB Output is correct
10 Correct 12 ms 24140 KB Output is correct
11 Correct 12 ms 24020 KB Output is correct
12 Correct 13 ms 23984 KB Output is correct
13 Correct 13 ms 24092 KB Output is correct
14 Correct 13 ms 24236 KB Output is correct
15 Correct 12 ms 24148 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 107484 KB Output is correct
2 Correct 707 ms 107456 KB Output is correct
3 Correct 767 ms 104252 KB Output is correct
4 Correct 797 ms 106660 KB Output is correct
5 Correct 597 ms 89040 KB Output is correct
6 Correct 773 ms 107788 KB Output is correct
7 Correct 831 ms 107072 KB Output is correct
8 Correct 835 ms 107720 KB Output is correct
9 Correct 801 ms 106812 KB Output is correct
10 Correct 722 ms 106852 KB Output is correct
11 Correct 536 ms 107980 KB Output is correct
12 Correct 496 ms 107536 KB Output is correct
13 Correct 547 ms 105664 KB Output is correct
14 Correct 491 ms 109980 KB Output is correct
15 Correct 75 ms 37096 KB Output is correct
16 Correct 692 ms 99712 KB Output is correct
17 Correct 544 ms 89748 KB Output is correct
18 Correct 632 ms 91776 KB Output is correct
19 Correct 744 ms 110964 KB Output is correct
20 Correct 847 ms 116796 KB Output is correct
21 Correct 674 ms 106808 KB Output is correct
22 Correct 674 ms 107572 KB Output is correct