제출 #837034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837034		Ozy	Mergers (JOI19_mergers)	C++17	0 / 100	68 ms	22956 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define pll pair<lli,lli>

#define MAX 500000

lli n,a,b,k,cont,general,res,raiz;
vector<lli> hijos[MAX+2];
lli id_g[MAX+2],e_g[MAX+2],todos[MAX+2],sub[MAX+2],activos[MAX+2],marcados[MAX+2],mm[MAX+2];
pll euler[MAX+2];

void suma(lli g) {
    activos[g]++;
    if(activos[g] == 1) general++;
    if(activos[g] == todos[g]) general--;
}

void dfs1(lli pos, lli padre,lli keep) { //tiene que ser con un small to large
    lli bigchlid = -1;
    lli tam = 0;
    for(auto h : hijos[pos]) {
        if(h == padre) continue;
        if(tam < sub[h]) {
            tam = sub[h];
            bigchlid = h;
        }
    }

    for(auto h : hijos[pos]) {
        if(h == padre || h == bigchlid) continue;
        dfs1(h,pos,0);
    }
    if (bigchlid != -1) {
        dfs1(bigchlid,pos,1);
        rep(i,euler[pos].first, euler[bigchlid].first - 1) suma(e_g[i]);
        rep(i,euler[bigchlid].second+1, euler[pos].second) suma(e_g[i]);
    }
    else suma(id_g[pos]);

    for(auto h : hijos[pos]){
        if(h == padre) continue;
        mm[pos] += mm[h];
    }
    
    if(general == 0) {
        marcados[pos] = 1;
        mm[pos]++;
    }

    if (!keep) { //confirmar que se resta del vector correspondiente (grupo esta incorrecto)
        rep(i,euler[pos].first, euler[pos].second) activos[e_g[i]] = 0;
        general = 0;
    }
}

void eul(lli pos,lli padre) {
    e_g[cont] = id_g[pos];
    euler[pos].first = cont++;
    sub[pos] = 1; 
    for(auto h : hijos[pos]) {
        if (h == padre) continue;
        eul(h,pos);
        sub[pos] += sub[h];
    }
    euler[pos].second = cont-1;
}

bool dfs2(lli pos, lli padre) {
    bool respuesta = false; 
    for(auto h : hijos[pos]) {
        if(h == padre) continue;
        respuesta |= dfs2(h,pos);
    }

    if(!respuesta && marcados[pos]) {
        res++;
        respuesta=true;
    }
    return respuesta;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
    }
    raiz = 1;
    rep(i,1,n) {
        if(hijos[i].size() > 1) {
            raiz = i;
            break;
        }
    }

    rep(i,1,n) {
        cin >> id_g[i];
        todos[id_g[i]]++;
    }

    cont = 1;
    eul(raiz,0);
    dfs1(raiz,0,0);
    marcados[raiz] = 0;

    //aqui tengo que partir de alguan arista que contengaotro
    rep(i,1,n) {
        if(mm[i] > 0 && mm[i] < mm[raiz]) {
            raiz = i;
            break;
        }
    }
    cont = 1;
    eul(raiz,0);
    dfs1(raiz,0,1);
    marcados[raiz] = 0;

    //correcto
    //ya que tengo aquella aristas que no cumplen, me falta encontrar la forma optima de emparejarlos

    dfs2(raiz,0);

    res++;
    res/=2;
    cout << res;
    return 0;  
}

//tener cuidado con los casos donde n=1 y n=2

//tener cuidado con el small to large
//tener cuidado con el euler tour y como estan las arignaciones
//tener cuidado con aquello que esta marcado y aquello que no
//comprobar si en serio es la idea la que esta incorrecta

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