Submission #837006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
837006	2023-08-24T19:38:33 Z	Ozy	Mergers (JOI19_mergers)	C++17	10 / 100	66 ms	26316 KB

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];
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);
    }
    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,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
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	11988 KB	Output is correct
2	Correct	5 ms	11988 KB	Output is correct
3	Correct	6 ms	11988 KB	Output is correct
4	Correct	5 ms	11988 KB	Output is correct
5	Correct	5 ms	11988 KB	Output is correct
6	Correct	6 ms	12116 KB	Output is correct
7	Correct	5 ms	12164 KB	Output is correct
8	Correct	5 ms	12116 KB	Output is correct
9	Correct	5 ms	11988 KB	Output is correct
10	Correct	5 ms	11988 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	11988 KB	Output is correct
14	Correct	6 ms	12116 KB	Output is correct
15	Correct	5 ms	12040 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	6 ms	12116 KB	Output is correct
18	Correct	6 ms	12116 KB	Output is correct
19	Correct	5 ms	11988 KB	Output is correct
20	Correct	6 ms	12048 KB	Output is correct
21	Correct	6 ms	12116 KB	Output is correct
22	Correct	6 ms	12116 KB	Output is correct
23	Correct	6 ms	12116 KB	Output is correct
24	Correct	6 ms	12116 KB	Output is correct

Subtask #2
0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	11988 KB	Output is correct
2	Correct	5 ms	11988 KB	Output is correct
3	Correct	6 ms	11988 KB	Output is correct
4	Correct	5 ms	11988 KB	Output is correct
5	Correct	5 ms	11988 KB	Output is correct
6	Correct	6 ms	12116 KB	Output is correct
7	Correct	5 ms	12164 KB	Output is correct
8	Correct	5 ms	12116 KB	Output is correct
9	Correct	5 ms	11988 KB	Output is correct
10	Correct	5 ms	11988 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	11988 KB	Output is correct
14	Correct	6 ms	12116 KB	Output is correct
15	Correct	5 ms	12040 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	6 ms	12116 KB	Output is correct
18	Correct	6 ms	12116 KB	Output is correct
19	Correct	5 ms	11988 KB	Output is correct
20	Correct	6 ms	12048 KB	Output is correct
21	Correct	6 ms	12116 KB	Output is correct
22	Correct	6 ms	12116 KB	Output is correct
23	Correct	6 ms	12116 KB	Output is correct
24	Correct	6 ms	12116 KB	Output is correct
25	Correct	6 ms	12116 KB	Output is correct
26	Correct	7 ms	12372 KB	Output is correct
27	Correct	7 ms	12340 KB	Output is correct
28	Correct	7 ms	12500 KB	Output is correct
29	Correct	7 ms	12372 KB	Output is correct
30	Correct	7 ms	12372 KB	Output is correct
31	Correct	6 ms	12116 KB	Output is correct
32	Correct	6 ms	12500 KB	Output is correct
33	Correct	5 ms	12116 KB	Output is correct
34	Correct	6 ms	12372 KB	Output is correct
35	Correct	6 ms	12372 KB	Output is correct
36	Incorrect	7 ms	12372 KB	Output isn't correct
37	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	5 ms	11988 KB	Output is correct
3	Correct	6 ms	11988 KB	Output is correct
4	Correct	5 ms	11988 KB	Output is correct
5	Correct	5 ms	11988 KB	Output is correct
6	Correct	6 ms	12116 KB	Output is correct
7	Correct	5 ms	12164 KB	Output is correct
8	Correct	5 ms	12116 KB	Output is correct
9	Correct	5 ms	11988 KB	Output is correct
10	Correct	5 ms	11988 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	11988 KB	Output is correct
14	Correct	6 ms	12116 KB	Output is correct
15	Correct	5 ms	12040 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	6 ms	12116 KB	Output is correct
18	Correct	6 ms	12116 KB	Output is correct
19	Correct	5 ms	11988 KB	Output is correct
20	Correct	6 ms	12048 KB	Output is correct
21	Correct	6 ms	12116 KB	Output is correct
22	Correct	6 ms	12116 KB	Output is correct
23	Correct	6 ms	12116 KB	Output is correct
24	Correct	6 ms	12116 KB	Output is correct
25	Correct	6 ms	12116 KB	Output is correct
26	Correct	36 ms	21344 KB	Output is correct
27	Correct	51 ms	21076 KB	Output is correct
28	Correct	7 ms	12372 KB	Output is correct
29	Correct	6 ms	12116 KB	Output is correct
30	Correct	5 ms	12116 KB	Output is correct
31	Correct	51 ms	21252 KB	Output is correct
32	Correct	7 ms	12372 KB	Output is correct
33	Correct	57 ms	26316 KB	Output is correct
34	Correct	47 ms	21068 KB	Output is correct
35	Incorrect	7 ms	12404 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	19864 KB	Output is correct
2	Correct	39 ms	22288 KB	Output is correct
3	Correct	7 ms	12372 KB	Output is correct
4	Correct	6 ms	12372 KB	Output is correct
5	Correct	6 ms	12020 KB	Output is correct
6	Correct	6 ms	12116 KB	Output is correct
7	Correct	7 ms	12400 KB	Output is correct
8	Correct	66 ms	22988 KB	Output is correct
9	Incorrect	9 ms	12372 KB	Output isn't correct
10	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	5 ms	11988 KB	Output is correct
3	Correct	6 ms	11988 KB	Output is correct
4	Correct	5 ms	11988 KB	Output is correct
5	Correct	5 ms	11988 KB	Output is correct
6	Correct	6 ms	12116 KB	Output is correct
7	Correct	5 ms	12164 KB	Output is correct
8	Correct	5 ms	12116 KB	Output is correct
9	Correct	5 ms	11988 KB	Output is correct
10	Correct	5 ms	11988 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	11988 KB	Output is correct
14	Correct	6 ms	12116 KB	Output is correct
15	Correct	5 ms	12040 KB	Output is correct
16	Correct	6 ms	11988 KB	Output is correct
17	Correct	6 ms	12116 KB	Output is correct
18	Correct	6 ms	12116 KB	Output is correct
19	Correct	5 ms	11988 KB	Output is correct
20	Correct	6 ms	12048 KB	Output is correct
21	Correct	6 ms	12116 KB	Output is correct
22	Correct	6 ms	12116 KB	Output is correct
23	Correct	6 ms	12116 KB	Output is correct
24	Correct	6 ms	12116 KB	Output is correct
25	Correct	6 ms	12116 KB	Output is correct
26	Correct	7 ms	12372 KB	Output is correct
27	Correct	7 ms	12340 KB	Output is correct
28	Correct	7 ms	12500 KB	Output is correct
29	Correct	7 ms	12372 KB	Output is correct
30	Correct	7 ms	12372 KB	Output is correct
31	Correct	6 ms	12116 KB	Output is correct
32	Correct	6 ms	12500 KB	Output is correct
33	Correct	5 ms	12116 KB	Output is correct
34	Correct	6 ms	12372 KB	Output is correct
35	Correct	6 ms	12372 KB	Output is correct
36	Incorrect	7 ms	12372 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Submission #837006

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0 / 24.0

Subtask #3 0 / 14.0

Subtask #4 0 / 22.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
0 / 24.0

Subtask #3
0 / 14.0

Subtask #4
0 / 22.0

Subtask #5
0 / 30.0