Submission #1126750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126750		Zero_OP	Pastiri (COI20_pastiri)	C++20	49 / 100	1097 ms	63564 KiB

pastiri

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 5e5 + 5;

int N, K, vt[MAX], best[MAX], min_dist[MAX], depth[MAX];
vector<int> adj[MAX], candidates;
bool vis[MAX];

void dfs(int u, int p, int median){
    if(depth[median] + min_dist[median] < depth[u] + min_dist[u]){
        median = u;
    }

    best[u] = median;
    for(auto v : adj[u]) if(v != p){
        depth[v] = depth[u] + 1;
        dfs(v, u, median);
    }
}

void color(int u, int p){
    vis[u] = true;
    for(auto v : adj[u]) if(v != p && min_dist[v] + 1 == min_dist[u]){
        color(v, u);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    file("task");

    cin >> N >> K;
    for(int i = 1; i < N; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= K; ++i){
        cin >> vt[i];
    }

    if(K == 1){
        cout << 1 << ' ' << 1 << '\n';
        return 0;
    }

    queue<int> q;
    memset(min_dist, -1, sizeof(min_dist));
    for(int i = 1; i <= K; ++i){
        q.push(vt[i]);
        min_dist[vt[i]] = 0;
    }

    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto v : adj[u]){
            if(min_dist[v] == -1){
                min_dist[v] = min_dist[u] + 1;
                q.push(v);
            }
        }
    }

    int rt = vt[1];
    dfs(rt, -1, rt);

    sort(vt + 1, vt + 1 + K, [&](int u, int v){ return depth[u] > depth[v]; });

    vector<int> ans;
    for(int i = 1; i <= K; ++i) if(!vis[vt[i]]){
        color(best[vt[i]], -1);
        ans.emplace_back(best[vt[i]]);
    }

    cout << sz(ans) << '\n';
    for(auto u : ans) cout << u << ' ';

    return 0;
}

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:10:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:65:5: note: in expansion of macro 'file'
   65 |     file("task");
      |     ^~~~
pastiri.cpp:10:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:65:5: note: in expansion of macro 'file'
   65 |     file("task");
      |     ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51