oj.uz

Submission #1023320

# Submission time Handle Problem Language Result Execution time Memory
1023320 2024-07-14T15:40:13 Z MarwenElarbi Pastiri (COI20_pastiri) C++17
100 / 100
 493 ms 115352 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define ll long long
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=5e5+5;
vector<int> adj[nax];
bool sheep[nax];
bool removed[nax];
bool ans[nax];
int sz[nax];
int dep[nax];
int dp[20][nax];
vector<pair<int,int>> parent[nax];
int dis[nax];
queue<pair<int,int>> q;
void bfs(){
    while(!q.empty()){
        auto cur=q.front();
        q.pop();
        for(auto u:adj[cur.se]){
            if(dis[u]>cur.fi+1){
                dis[u]=cur.fi+1;
                q.push({cur.fi+1,u});
            }
        }
    }
}
void dfs(int x,int p){
    for (int i = 1; i < 20; ++i)
    {
        dp[i][x]=dp[i-1][dp[i-1][x]];
    }
    for(auto u:adj[x]){
        if(u==p) continue;
        dep[u]=dep[x]+1;
        dp[0][u]=x;
        dfs(u,x);
    }
    return;
}
int jump(int x,int d){
    for (int i = 19; i >= 0; --i)
    {
        if(d&(1<<i)) x=dp[i][x];
    }
    return x;
}
bool compare(int x,int y){
    return dep[x]<dep[y];
}
bool vis[nax];
void dfs2(int x){
    vis[x]=true;
    for(auto u:adj[x]){
        if(vis[u]) continue;
        if(dis[x]==dis[u]+1) dfs2(u);
    }
}
signed main(){
    iostream::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    vector<int> tab(k);
    for (int i = 0; i < n; ++i)
    {
        dis[i]=1e9;
    }
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for (int i = 0; i < k; ++i)
    {
        int x;
        cin>>x;
        tab[i]=x-1;
        sheep[--x]=true;
        dis[x]=0;
        q.push({0,x});
    }
    bfs();
    for (int i = 0; i < n; ++i)
    {
        for(auto u:parent[i]){
            dis[i]=min(dis[i],u.se+dis[u.fi]);
        }
    }
    dfs(0,-1);
    sort(tab.rbegin(),tab.rend(),compare);
    for (int i = 0; i < k; ++i)
    {
        if(vis[tab[i]]) continue;
        int cur=0;
        for (int j = 19; j >= 0; --j)
        {
            cur+=(1<<j);
            if(dis[dp[j][tab[i]]]==cur) tab[i]=dp[j][tab[i]];
            else cur-=(1<<j);
        }
        ans[tab[i]]=1;
        dfs2(tab[i]);
    }
    vector<int> cnt;
    for (int i = 0; i < n; ++i)
    {
        if(ans[i]==1) cnt.pb(i);
    }
    cout <<cnt.size()<<endl;
    for (int i = 0; i < cnt.size(); ++i)
    {
        cout <<cnt[i]+1<<" ";
    }cout <<endl;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < cnt.size(); ++i)
      |                     ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 106948 KB Output is correct
2 Correct 165 ms 107604 KB Output is correct
3 Correct 165 ms 107604 KB Output is correct
4 Correct 257 ms 115352 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25692 KB Output is correct
2 Correct 12 ms 25688 KB Output is correct
3 Correct 325 ms 91624 KB Output is correct
4 Correct 288 ms 93996 KB Output is correct
5 Correct 385 ms 90852 KB Output is correct
6 Correct 440 ms 92384 KB Output is correct

Subtask #3
23.0 / 23.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 92008 KB Output is correct
2 Correct 369 ms 91984 KB Output is correct
3 Correct 446 ms 96444 KB Output is correct
4 Correct 366 ms 91216 KB Output is correct
5 Correct 369 ms 83144 KB Output is correct
6 Correct 444 ms 99428 KB Output is correct
7 Correct 486 ms 97872 KB Output is correct
8 Correct 483 ms 97228 KB Output is correct
9 Correct 493 ms 91240 KB Output is correct
10 Correct 396 ms 90864 KB Output is correct
11 Correct 337 ms 93964 KB Output is correct
12 Correct 293 ms 97712 KB Output is correct
13 Correct 306 ms 99644 KB Output is correct
14 Correct 259 ms 95248 KB Output is correct
15 Correct 41 ms 36184 KB Output is correct
16 Correct 393 ms 86500 KB Output is correct
17 Correct 399 ms 83400 KB Output is correct
18 Correct 316 ms 79320 KB Output is correct
19 Correct 404 ms 95436 KB Output is correct
20 Correct 438 ms 96804 KB Output is correct
21 Correct 300 ms 90916 KB Output is correct
22 Correct 315 ms 91472 KB Output is correct