oj.uz

Submission #1023194

# Submission time Handle Problem Language Result Execution time Memory
1023194 2024-07-14T12:56:30 Z MarwenElarbi Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 253128 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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];
int get_size(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(u==p||removed[u]) continue;
        sz[x]+=get_size(u,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(removed[u]||u==p) continue;
        if(sz[u]*2>t_sz) return get_centroid(u,t_sz,x);
    }
    return x;
}
int cur=0;
void get_dist(int x,int p,int centroid){
    if(sheep[x]) dis[centroid]=min(dis[centroid],cur);
    for(auto u:adj[x]){
        if(removed[u]||u==p) continue;
        cur++;
        get_dist(u,x,centroid);
        cur--;
    }
    parent[x].pb({centroid,cur});
}
void build(int x){
    int centroid=get_centroid(x,get_size(x,-1),-1);
    get_dist(centroid,-1,centroid);
    removed[centroid]=1;
    for(auto u:adj[centroid]){
        if(removed[u]) continue;
        build(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;
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    x=jump(x,dep[x]-dep[y]);
    if(x==y) return x;
    for (int i = 19; i >= 0; --i)
    {
        if(dp[i][x]!=dp[i][y]){
            x=dp[i][x];
            y=dp[i][y];
        }
    }
    return dp[x][0];
}
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;
    }
    build(0);
    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 l=0;
        int r=dep[tab[i]];
        while(r-l>1){
            int mid=(r+l)/2;
            if(dis[jump(tab[i],mid)]==mid) l=mid;
            else r=mid;
        }
        ans[jump(tab[i],l)]=1;
        dfs2(jump(tab[i],l));
    }
    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:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (int i = 0; i < cnt.size(); ++i)
      |                     ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 246016 KB Output is correct
2 Correct 544 ms 247376 KB Output is correct
3 Correct 583 ms 247632 KB Output is correct
4 Correct 752 ms 253128 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 25180 KB Output is correct
2 Correct 15 ms 25192 KB Output is correct
3 Execution timed out 1046 ms 162384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24412 KB Output is correct
2 Correct 13 ms 24408 KB Output is correct
3 Correct 13 ms 24412 KB Output is correct
4 Correct 11 ms 24412 KB Output is correct
5 Correct 12 ms 24668 KB Output is correct
6 Correct 12 ms 24412 KB Output is correct
7 Correct 13 ms 24664 KB Output is correct
8 Correct 13 ms 24664 KB Output is correct
9 Correct 13 ms 24412 KB Output is correct
10 Correct 12 ms 24412 KB Output is correct
11 Correct 12 ms 24392 KB Output is correct
12 Correct 12 ms 24152 KB Output is correct
13 Correct 13 ms 24412 KB Output is correct
14 Correct 13 ms 24668 KB Output is correct
15 Correct 13 ms 24580 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 103860 KB Time limit exceeded
2 Halted 0 ms 0 KB -