oj.uz

Submission #837050

# Submission time Handle Problem Language Result Execution time Memory
837050 2023-08-24T20:30:38 Z Ozy Mergers (JOI19_mergers) C++17
0 / 100
 84 ms 23036 KB 
#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);
    if(marcados[raiz] == 1) {
        marcados[raiz] = 0;
        mm[raiz]--;
    }

    //aqui tengo que partir de alguan arista que contengaotro
    rep(i,1,n) {
        if(hijos[i].size() == 1) continue;
        if(mm[i] > 0 && mm[i] < mm[raiz]) {
            raiz = i;
            break;
        }
    }

    rep(i,1,n) {
        mm[i] = 0;
        marcados[i] = 0;
    }

    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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12128 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 5 ms 12116 KB Output is correct
8 Correct 5 ms 12116 KB Output is correct
9 Correct 5 ms 12116 KB Output is correct
10 Correct 5 ms 12116 KB Output is correct
11 Correct 5 ms 12116 KB Output is correct
12 Correct 5 ms 12116 KB Output is correct
13 Correct 5 ms 12116 KB Output is correct
14 Incorrect 5 ms 12124 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12128 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 5 ms 12116 KB Output is correct
8 Correct 5 ms 12116 KB Output is correct
9 Correct 5 ms 12116 KB Output is correct
10 Correct 5 ms 12116 KB Output is correct
11 Correct 5 ms 12116 KB Output is correct
12 Correct 5 ms 12116 KB Output is correct
13 Correct 5 ms 12116 KB Output is correct
14 Incorrect 5 ms 12124 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12128 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 5 ms 12116 KB Output is correct
8 Correct 5 ms 12116 KB Output is correct
9 Correct 5 ms 12116 KB Output is correct
10 Correct 5 ms 12116 KB Output is correct
11 Correct 5 ms 12116 KB Output is correct
12 Correct 5 ms 12116 KB Output is correct
13 Correct 5 ms 12116 KB Output is correct
14 Incorrect 5 ms 12124 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 21496 KB Output is correct
2 Correct 44 ms 23036 KB Output is correct
3 Correct 7 ms 12372 KB Output is correct
4 Correct 7 ms 12372 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 5 ms 12116 KB Output is correct
7 Correct 6 ms 12420 KB Output is correct
8 Correct 84 ms 22092 KB Output is correct
9 Correct 7 ms 12372 KB Output is correct
10 Correct 66 ms 21336 KB Output is correct
11 Incorrect 5 ms 12116 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12128 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 5 ms 12116 KB Output is correct
8 Correct 5 ms 12116 KB Output is correct
9 Correct 5 ms 12116 KB Output is correct
10 Correct 5 ms 12116 KB Output is correct
11 Correct 5 ms 12116 KB Output is correct
12 Correct 5 ms 12116 KB Output is correct
13 Correct 5 ms 12116 KB Output is correct
14 Incorrect 5 ms 12124 KB Output isn't correct
15 Halted 0 ms 0 KB -