Submission #921298

#	Time	Username	Problem	Language	Result	Execution time	Memory
921298		ErJ	Pastiri (COI20_pastiri)	C++17	100 / 100	652 ms	66904 KiB

pastiri

#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 (stderr)

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 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51