Submission #398121

#	Time	Username	Problem	Language	Result	Execution time	Memory
398121		Dremix10	Pastiri (COI20_pastiri)	C++17	8 / 100	337 ms	91496 KiB

pastiri

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int N = 5e5+1;

vector<vector<int> > a(N);
bool sheep[N];
int d[N],path[N],guard[N];
vector<int> ans;

void dfs(int s, int e){
    guard[s] = s;
    path[s] = e;
    if(!sheep[s])
        d[s] = -1;
    vector<pi> arr;
    for(auto x : a[s]){
        if(x == e)continue;
        dfs(x,s);
        if(d[x] != -1)
            arr.push_back({d[x]+1,guard[x]});
    }
    if(sz(arr) == 1){
        if(arr[0].F % 2 == 0)
            arr[0].S = path[arr[0].S];
        if(!d[s]){
            ans.push_back(arr[0].S);
            if(arr[0].F % 2 == 0)
                d[s] = -1;
        }
        else{
            d[s] = arr[0].F;
            guard[s] = arr[0].S;
        }
    }
    else if(sz(arr) == 2){
        if(arr[0].F > arr[1].F)
            swap(arr[0],arr[1]);
        if(!d[s]){
            for(auto x : arr){
                if(x.F % 2 == 0){
                    x.S = path[x.S];
                    d[s] = -1;
                }
                ans.push_back(x.S);
            }
        }
        else{
            int dist = arr[0].F + arr[1].F;
            if(dist % 2){
                ans.push_back(arr[0].S);
                ans.push_back(arr[1].S);
                return;
            }
            dist -= arr[1].F;
            dist = (dist+1)/2;
            while(dist--)
                arr[1].S = path[arr[1].S];
            ans.push_back(arr[1].S);
        }
    }
    else
        assert(sz(arr) == 0);
}

int main(){
fastio

int n,k;
cin>>n>>k;

int i;

for(i=0;i<n-1;i++){
    int x,y;
    cin>>x>>y;
    a[x].push_back(y);
    a[y].push_back(x);
}

for(i=0;i<k;i++){
    int x;cin>>x;
    sheep[x] = true;
}

dfs(1,1);
if(d[1] != -1)
    ans.push_back(guard[1]);

cout<<sz(ans)<<endl;
for(auto x : ans)
    cout<<x<<" ";



}

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