Submission #674958

#	Time	Username	Problem	Language	Result	Execution time	Memory
674958		MohamedFaresNebili	Pastiri (COI20_pastiri)	C++14	100 / 100	699 ms	85296 KiB

pastiri

#include <bits/stdc++.h>

        using namespace std;

        int N, K, A[500005];
        int P[500005], D[500005], G[500005];
        vector<int> adj[500005];
        set<pair<int, int>> S;
        bool vis[500005];

        void dfs(int v, int p) {
            D[v] = D[p] + 1; P[v] = p;
            for(auto u : adj[v]) {
                if(u == p) continue;
                dfs(u, v);
            }
        }
        void solve(int v) {
            if(vis[v]) return;
            vis[v] = 1;
            for(auto u : adj[v]) {
                if(vis[u]) continue;
                if(G[u] + 1 == G[v])
                    solve(u);
            }
        }

		int32_t main() {
			ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
			cin >> N >> K;
			for(int l = 1; l <= N - 1; l++) {
                int U, V; cin >> U >> V;
                adj[U].push_back(V);
                adj[V].push_back(U);
            }
            D[1] = -1; dfs(1, 1); queue<int> Q;
            for(int l = 1; l <= N; l++) G[l] = 1e9 + 7;
            for(int l = 1; l <= K; l++) {
                cin >> A[l]; Q.push(A[l]);
                S.insert({-D[A[l]], A[l]});
                G[A[l]] = 0;
            }
            while(!Q.empty()) {
                int U = Q.front(); Q.pop();
                for(auto V : adj[U]) {
                    if(G[V] > G[U] + 1) {
                        G[V] = G[U] + 1;
                        Q.push(V);
                    }
                }
            }
            vector<int> res;
            for(auto u : S) {
                int U = u.second, V = u.second;
                if(vis[U]) continue;
                while(V != 1 && (G[P[V]] == D[U] - D[P[V]])) V = P[V];
                res.push_back(V); solve(V);
            }
            cout << (int)res.size() << "\n";
            for(int l = 0; l < res.size(); l++) {
                if(l > 0) cout << " ";
                cout << res[l];
            }
            cout << "\n";
		}

Compilation message (stderr)

pastiri.cpp: In function 'int32_t main()':
pastiri.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for(int l = 0; l < res.size(); l++) {
      |                            ~~^~~~~~~~~~~~

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