oj.uz

Submission #1023201

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 246100 KB Output is correct
2 Correct 606 ms 247376 KB Output is correct
3 Correct 693 ms 247380 KB Output is correct
4 Correct 860 ms 253132 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25180 KB Output is correct
2 Correct 16 ms 25180 KB Output is correct
3 Execution timed out 1091 ms 117760 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 13 ms 24412 KB Output is correct
3 Correct 13 ms 24412 KB Output is correct
4 Correct 14 ms 24368 KB Output is correct
5 Correct 13 ms 24668 KB Output is correct
6 Correct 14 ms 24580 KB Output is correct
7 Correct 13 ms 24668 KB Output is correct
8 Correct 18 ms 24664 KB Output is correct
9 Correct 18 ms 24412 KB Output is correct
10 Correct 14 ms 24668 KB Output is correct
11 Correct 13 ms 24408 KB Output is correct
12 Correct 14 ms 24152 KB Output is correct
13 Correct 13 ms 24412 KB Output is correct
14 Correct 14 ms 24700 KB Output is correct
15 Correct 14 ms 24668 KB Output is correct

Subtask #4
0 / 51.0

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