oj.uz

Submission #755521

# Submission time Handle Problem Language Result Execution time Memory
755521 2023-06-10T08:15:50 Z vjudge1 Pastiri (COI20_pastiri) C++17
100 / 100
 911 ms 85316 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 153 ms 63692 KB Output is correct
2 Correct 190 ms 64232 KB Output is correct
3 Correct 220 ms 64132 KB Output is correct
4 Correct 536 ms 85316 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 9 ms 12340 KB Output is correct
3 Correct 396 ms 41004 KB Output is correct
4 Correct 400 ms 43324 KB Output is correct
5 Correct 541 ms 40784 KB Output is correct
6 Correct 721 ms 42932 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12220 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 7 ms 12220 KB Output is correct
4 Correct 8 ms 12204 KB Output is correct
5 Correct 8 ms 12220 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 12116 KB Output is correct
9 Correct 8 ms 12216 KB Output is correct
10 Correct 9 ms 12132 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 8 ms 12116 KB Output is correct
13 Correct 8 ms 12244 KB Output is correct
14 Correct 9 ms 12212 KB Output is correct
15 Correct 7 ms 12196 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 41988 KB Output is correct
2 Correct 501 ms 42088 KB Output is correct
3 Correct 629 ms 54536 KB Output is correct
4 Correct 593 ms 40828 KB Output is correct
5 Correct 568 ms 48856 KB Output is correct
6 Correct 911 ms 63284 KB Output is correct
7 Correct 766 ms 57904 KB Output is correct
8 Correct 759 ms 55728 KB Output is correct
9 Correct 705 ms 40848 KB Output is correct
10 Correct 550 ms 40744 KB Output is correct
11 Correct 372 ms 43344 KB Output is correct
12 Correct 443 ms 55888 KB Output is correct
13 Correct 629 ms 62692 KB Output is correct
14 Correct 274 ms 44348 KB Output is correct
15 Correct 91 ms 17844 KB Output is correct
16 Correct 674 ms 39744 KB Output is correct
17 Correct 582 ms 49656 KB Output is correct
18 Correct 604 ms 35592 KB Output is correct
19 Correct 653 ms 49484 KB Output is correct
20 Correct 564 ms 50228 KB Output is correct
21 Correct 450 ms 40908 KB Output is correct
22 Correct 445 ms 41444 KB Output is correct