Submission #441648

#	Time	Username	Problem	Language	Result	Execution time	Memory
441648		JovanB	Mergers (JOI19_mergers)	C++17	100 / 100	1314 ms	132312 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MAXN = 500000;
const int MXLOG = 19;

int in[MAXN+5];
int out[MAXN+5];
int svih[MAXN+5];
int kome[MAXN+5];
vector <int> graf[MAXN+5];
int par[MAXN+5][MXLOG+1];

int tjm;

int depth[MAXN+5];

void dfs_calc(int v, int p){
    in[v] = ++tjm;
    par[v][0] = p;
    depth[v] = depth[p] + 1;
    for(int j=1; j<=MXLOG; j++) par[v][j] = par[par[v][j-1]][j-1];
    for(auto c : graf[v]) if(c != p) dfs_calc(c, v);
    out[v] = tjm;
}

bool is_parent(int a, int b){
    return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]);
}

int lca(int a, int b){
    if(is_parent(a, b)) return a;
    for(int j=MXLOG; j>=0; j--) if(!is_parent(par[a][j], b)) a = par[a][j];
    return par[a][0];
}

bool deli[MAXN+5];

int dfs_traverse(int v, int p){
    int mnh = depth[svih[kome[v]]];
    for(auto c : graf[v]) if(c != p) mnh = min(mnh, dfs_traverse(c, v));
    if(mnh >= depth[v]) deli[v] = 1;
    return mnh;
}

vector <int> dgraf[MAXN+5];

void dfs_final(int v, int p, int lst){
    int sd = lst;
    if(deli[v]){
        if(lst){
            dgraf[lst].push_back(v);
            dgraf[v].push_back(lst);
        }
        sd = v;
    }
    for(auto c : graf[v]) if(c != p) dfs_final(c, v, sd);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, k;
    cin >> n >> k;
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs_calc(1, 0);
    for(int i=1; i<=n; i++){
        cin >> kome[i];
        if(!svih[kome[i]]) svih[kome[i]] = i;
        else svih[kome[i]] = lca(svih[kome[i]], i);
    }
    dfs_traverse(1, 0);
    dfs_final(1, 0, 0);
    int leaves = 0;
    for(int i=1; i<=n; i++) leaves += (dgraf[i].size() == 1);
    cout << (leaves+1)/2 << "\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30