oj.uz

답안 #1023176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1023176 2024-07-14T11:55:16 Z MarwenElarbi Pastiri (COI20_pastiri) C++17
0 / 100
 1000 ms 247040 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];
}
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)
    {
        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;
    }
    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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 559 ms 245844 KB Output is correct
2 Incorrect 579 ms 247040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 25176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 24408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1065 ms 103040 KB Time limit exceeded
2 Halted 0 ms 0 KB -