oj.uz

Submission #674958

# Submission time Handle Problem Language Result Execution time Memory
674958 2022-12-26T17:12:28 Z MohamedFaresNebili Pastiri (COI20_pastiri) C++14
100 / 100
 699 ms 85296 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 63812 KB Output is correct
2 Correct 172 ms 64196 KB Output is correct
3 Correct 183 ms 64208 KB Output is correct
4 Correct 487 ms 85296 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12376 KB Output is correct
2 Correct 8 ms 12372 KB Output is correct
3 Correct 376 ms 41076 KB Output is correct
4 Correct 364 ms 43328 KB Output is correct
5 Correct 505 ms 40744 KB Output is correct
6 Correct 623 ms 42840 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12116 KB Output is correct
2 Correct 7 ms 12216 KB Output is correct
3 Correct 7 ms 12244 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 8 ms 12272 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12088 KB Output is correct
9 Correct 7 ms 12216 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 8 ms 12160 KB Output is correct
13 Correct 7 ms 12244 KB Output is correct
14 Correct 7 ms 12252 KB Output is correct
15 Correct 7 ms 12256 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 42036 KB Output is correct
2 Correct 480 ms 41948 KB Output is correct
3 Correct 628 ms 54368 KB Output is correct
4 Correct 505 ms 40832 KB Output is correct
5 Correct 507 ms 49008 KB Output is correct
6 Correct 699 ms 63452 KB Output is correct
7 Correct 659 ms 57920 KB Output is correct
8 Correct 673 ms 55860 KB Output is correct
9 Correct 629 ms 40724 KB Output is correct
10 Correct 492 ms 40864 KB Output is correct
11 Correct 347 ms 43412 KB Output is correct
12 Correct 415 ms 55776 KB Output is correct
13 Correct 608 ms 62620 KB Output is correct
14 Correct 284 ms 44496 KB Output is correct
15 Correct 55 ms 17804 KB Output is correct
16 Correct 541 ms 39772 KB Output is correct
17 Correct 494 ms 49652 KB Output is correct
18 Correct 488 ms 35788 KB Output is correct
19 Correct 560 ms 49608 KB Output is correct
20 Correct 521 ms 50276 KB Output is correct
21 Correct 479 ms 40908 KB Output is correct
22 Correct 452 ms 41344 KB Output is correct