oj.uz

Submission #1023196

# Submission time Handle Problem Language Result Execution time Memory
1023196 2024-07-14T12:58:35 Z MarwenElarbi Pastiri (COI20_pastiri) C++17
31 / 100
 1000 ms 249036 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;
}
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;
        }
        tab[i]=jump(tab[i],l);
        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:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 0; i < cnt.size(); ++i)
      |                     ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 243024 KB Output is correct
2 Correct 574 ms 244308 KB Output is correct
3 Correct 571 ms 244308 KB Output is correct
4 Correct 768 ms 249036 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
23.0 / 23.0

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

Subtask #4
0 / 51.0

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