oj.uz

Submission #836950

# Submission time Handle Problem Language Result Execution time Memory
836950 2023-08-24T17:56:01 Z Ozy Mergers (JOI19_mergers) C++17
0 / 100
 41 ms 23960 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;
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];
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]);
    
    if(general == 0) marcados[pos] = 1;

    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);
    }
    rep(i,1,n) {
        cin >> id_g[i];
        todos[id_g[i]]++;
    }

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

    //rep(i,1,n) debug(marcados[i]);

    dfs2(1,0);

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

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 19840 KB Output is correct
2 Incorrect 41 ms 23960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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