oj.uz

Submission #921298

# Submission time Handle Problem Language Result Execution time Memory
921298 2024-02-03T16:38:22 Z ErJ Pastiri (COI20_pastiri) C++17
100 / 100
 652 ms 66904 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mpp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define mod 1000000007
#define rep(a, b) for(int a = 0; a < (b); a++)
#define inf 1000000000000000000

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    vvi edges(n);
    
    vi sheeps(n), dead(n), dist(n), straznik(n);
    rep(i, n) {
        sheeps[i] = -1;
        dead[i] = 0;
        dist[i] = inf;
        straznik[i] = -1;
    }
    for (int i = 0; i < n - 1; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    qp q;
    for (int i = 0; i < k; i++) {
        int a;
        cin >> a;
        a--;
        sheeps[a] = 0;
        dist[a] = 0;
        q.push({ a, 0 });
    }
    if (n == 1) {
        cout << 1 << endl;
        cout << 1 << endl;
    }
    while (!q.empty()) {
        ll u = q.front().first;
        ll d1 = q.front().second;
        q.pop();
        for (int v : edges[u]) {
            if (dist[v] == inf) {
                dist[v] = d1 + 1;
                q.push({ v, d1 + 1 });
            }
        }
    }
    ll ans = 0;
    vi deg(n);
    queue<ll> q1;
    rep(i, n) {
        deg[i] = edges[i].size();
        if (deg[i] == 1) {
            q1.push(i);
        }
    }
    vi ANS;
    while (!q1.empty()) {
        int u = q1.front();
        
        q1.pop();
        int parent = -2;
        for (int i = 0; i < edges[u].size(); i++) {
            if (dead[edges[u][i]] == 0) {
                parent = edges[u][i];
                break;
            }
        }
        if (parent == -2) {
            if ((sheeps[u] > -1)) {
                if (straznik[u] >= sheeps[u]) {
                    break;
                }
                ans++;
                ANS.push_back(u);
            }
            break;
        }
        if (straznik[u] == -1) { //not straznik
            if (sheeps[u] >= 0) { //is ovce
                if (sheeps[u] + 1 <= dist[parent]) {
                    sheeps[parent] = sheeps[u] + 1;
                    sheeps[u] = -1;
                }
                else {
                    ans++;
                    straznik[u] = sheeps[u];
                    sheeps[u] = -1;
                    ANS.push_back(u);
                    straznik[parent] = max(straznik[parent], straznik[u] - 1);
                    straznik[u] = -1;
                    // move straznika
                }
            }
            else { //not sheep
                dead[u] = 1; //nic tam neni - prohlasim za mrtveho.
            }
        }
        else { // je tu straznik
            if (straznik[u] >= sheeps[u]) {//strazim ovci
                sheeps[u] = -1;
            }
            if (sheeps[u] == -1) {
                if (straznik[u] >= 1) {
                    straznik[parent] = max(straznik[parent], straznik[u] - 1);
                    straznik[u] = -1;
                }
            }
            else {// there is sheep
                //both up
                if (sheeps[u] + 1 <= dist[parent]) { //sheep can go up.
                    straznik[parent] = max(straznik[parent], straznik[u] - 1);
                    sheeps[parent] = sheeps[u] + 1;
                    sheeps[u] = -1;
                }
                else { //sheep cant go up
                    straznik[u] = sheeps[u];
                    ans++;
                    sheeps[u] = -1;
                    straznik[parent] = max(straznik[parent], straznik[u] - 1);
                    straznik[u] = -1;
                    ANS.push_back(u);
                }
            }
        }
        dead[u] = 1;
        deg[parent]--;
        if (deg[parent] <= 1) {
            q1.push(parent);
        }
    }
    cout << ans << endl;
    for (int i = 0; i < ANS.size() - 1; i++) {
        cout << ANS[i] + 1 << " ";
    }
    cout << ANS[ANS.size() - 1] + 1 << endl;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < edges[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
pastiri.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0; i < ANS.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 53980 KB Output is correct
2 Correct 161 ms 54092 KB Output is correct
3 Correct 158 ms 53844 KB Output is correct
4 Correct 246 ms 62716 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 387 ms 59392 KB Output is correct
4 Correct 422 ms 64612 KB Output is correct
5 Correct 405 ms 53844 KB Output is correct
6 Correct 454 ms 54060 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 58196 KB Output is correct
2 Correct 487 ms 58016 KB Output is correct
3 Correct 484 ms 62924 KB Output is correct
4 Correct 402 ms 54100 KB Output is correct
5 Correct 382 ms 49608 KB Output is correct
6 Correct 604 ms 62664 KB Output is correct
7 Correct 652 ms 61816 KB Output is correct
8 Correct 537 ms 61388 KB Output is correct
9 Correct 501 ms 53976 KB Output is correct
10 Correct 407 ms 54036 KB Output is correct
11 Correct 358 ms 62296 KB Output is correct
12 Correct 364 ms 64720 KB Output is correct
13 Correct 331 ms 66904 KB Output is correct
14 Correct 411 ms 63896 KB Output is correct
15 Correct 95 ms 9812 KB Output is correct
16 Correct 424 ms 50264 KB Output is correct
17 Correct 253 ms 50884 KB Output is correct
18 Correct 529 ms 44284 KB Output is correct
19 Correct 528 ms 59320 KB Output is correct
20 Correct 465 ms 58312 KB Output is correct
21 Correct 441 ms 57944 KB Output is correct
22 Correct 432 ms 58388 KB Output is correct