제출 #1223437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223437		iulia_morariu	Pastiri (COI20_pastiri)	C++20	100 / 100	287 ms	70372 KiB

pastiri

#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
// #include <bits/stdc++.h>
#define in  cin
#define out cout

using namespace std;

vector<int> g[500001];
int niv[500001];
int dist[500001]; // dist minima pana la o oaie
int oi[500001];
int f[500001];
int n, m;
bool prt[500001]; // protejat (used protection :))

void fa_nivele(int nod){
    for(const int &x : g[nod]){
        if(x == f[nod]) continue;
        niv[x] = niv[nod] + 1;
        f[x] = nod;
        fa_nivele(x);
    }
}

bool cmp(const int &a, const int &b){
    return niv[a] > niv[b]; // de la leaf in sus kinda
}

void marcheaza(int nod, int d){ // d e ca un 'range' in care protejeaza oile
    prt[nod] = 1;
    for(const int &x : g[nod]){
        if(prt[x]) continue;
        if(dist[x] != d - 1) continue; // scade dist spre o oaie
        marcheaza(x, d - 1);
    }
}

vector<int> pastori;
void chiar_solve(){
    fa_nivele(1);
    queue<int> q; // un fel de bfs de la toate oile
    for(int i = 1; i <= n; i++) dist[i] = n + 10;
    for(int i = 0; i < m; i++){
        dist[ oi[i] ] = 0;
        q.push( oi[i] );
    }

    while(!q.empty()){
        int nod = q.front(); q.pop();
        for(const int &x : g[nod]){
            if( dist[x] > dist[nod] + 1 ){
                dist[x] = dist[nod] + 1;
                q.push(x);
            }
        }
    }

    // cout << "dist : "; // merge
    // for(int i = 1; i <= n; i++) cout << dist[i] << " ";
    // cout << '\n';

    sort(oi + 0, oi + m, cmp); // oile cele mai de jos
    /*
    ce osa fac e asa:
    zic ok, e aparata oaia i? - da : continue
    daca nu zic ok, o apar la pozitia ei. Cat de sus pot sa urc a.i. sa fie cea mai apropiata oaie de mine?
    cand ajung acolo like marchez toate restul oilor protejate si continui
    */

    for(int i = 0; i < m; i++){
        if(prt[ oi[i] ]) continue;
        int ps = oi[i];
        while(ps != 1 && dist[ps] + 1 == dist[ f[ps] ]){ // dist se incrementeaza cu cat urc
            ps = f[ps];
        }

        // cout << "Il fac pastor pe " << ps << " de la oaia " << oi[i] << '\n';
        pastori.push_back(ps);
        marcheaza(ps, niv[oi[i]] - niv[ps]);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    in >> n >> m;
    for(int i = 0; i < n - 1; i++){
        int a, b; in >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 0; i < m; i++) in >> oi[i];

    chiar_solve();

    out << pastori.size() << '\n';
    for(const int &x : pastori) out << x << " ";
    out << '\n';

    return 0;
}

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