oj.uz

Submission #1023206

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 246100 KB Output is correct
2 Correct 571 ms 247280 KB Output is correct
3 Correct 574 ms 247380 KB Output is correct
4 Correct 685 ms 253012 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 16 ms 25180 KB Output is correct
3 Execution timed out 1074 ms 161896 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 12 ms 24408 KB Output is correct
3 Correct 12 ms 24412 KB Output is correct
4 Correct 12 ms 24412 KB Output is correct
5 Correct 13 ms 24668 KB Output is correct
6 Correct 13 ms 24408 KB Output is correct
7 Correct 12 ms 24668 KB Output is correct
8 Correct 13 ms 24668 KB Output is correct
9 Correct 12 ms 24412 KB Output is correct
10 Correct 11 ms 24412 KB Output is correct
11 Correct 11 ms 24224 KB Output is correct
12 Correct 15 ms 24152 KB Output is correct
13 Correct 12 ms 24408 KB Output is correct
14 Correct 16 ms 24780 KB Output is correct
15 Correct 17 ms 24668 KB Output is correct

Subtask #4
0 / 51.0

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