avogadro.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <queue>

using namespace std;

int n;

typedef int int_1230997[1230997];

int_1230997 a, b, c, bb, cc, ma, cleared;

queue<int> qu;

main(){

    int i, u, answer=0;

    scanf("%d", &n);

    for (i=1; i<=n; i++) scanf("%d", &a[i]);

    for (i=1; i<=n; i++) scanf("%d", &b[i]);

    for (i=1; i<=n; i++) scanf("%d", &c[i]);

    for (i=1; i<=n; i++) bb[b[i]]++;

    for (i=1; i<=n; i++) cc[c[i]]++;

    for (i=1; i<=n; i++) ma[a[i]]=i;

    for (i=1; i<=n; i++) if (bb[i]==0) qu.push(i);

    for (i=1; i<=n; i++) if (cc[i]==0) qu.push(i);

    while (qu.size()){

        u=qu.front(); qu.pop();

        if (cleared[u]) continue;

        i = ma[u];

        bb[b[i]]--;

        cc[c[i]]--;

        if (bb[b[i]]==0) qu.push(b[i]);

        if (cc[c[i]]==0) qu.push(c[i]);

        cleared[u]=true;

        answer++;

    }

    printf("%d\n", answer);

}

Nhận xét