NOI批量评测 - 记录详情

#	状态分数	耗时	内存占用

#1	Accepted 5	2ms	404 KiB
#2	Accepted 5	2ms	400 KiB
#3	Accepted 5	1ms	548 KiB
#4	Accepted 5	1ms	404 KiB
#5	Accepted 5	3ms	404 KiB
#6	Accepted 5	3ms	404 KiB
#7	Accepted 5	116ms	3.4 MiB
#8	Accepted 5	109ms	3.3 MiB
#9	Accepted 5	3ms	408 KiB
#10	Accepted 5	3ms	404 KiB
#11	Accepted 5	123ms	3.5 MiB
#12	Accepted 5	115ms	3.3 MiB
#13	Accepted 5	3ms	404 KiB
#14	Accepted 5	3ms	404 KiB
#15	Accepted 5	124ms	4 MiB
#16	Accepted 5	113ms	3.8 MiB
#17	Accepted 5	3ms	404 KiB
#18	Accepted 5	3ms	404 KiB
#19	Accepted 5	114ms	3.4 MiB
#20	Accepted 5	110ms	3.4 MiB

#include <bits/stdc++.h>
typedef long long ll;
typedef double lf;
using namespace std;
const int INF = 1e9+7;
const int maxn = 1e5+5;
int T, n;
char a[maxn], b[maxn];
char t1[maxn], t2[maxn];
int faa[maxn], fab[maxn];
int cnta0[maxn], cnta1[maxn];
int cntb0[maxn], cntb1[maxn];

template <typename type>
void inline read(type &x){
    x = 0; type f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x*10+ch-'0', ch = getchar();
    x = x*f;
}

void init(){
    for (int i = 1; i <= n; i++){
        faa[i] = i;
        fab[i] = i;
        cnta0[i] = 0;
        cnta1[i] = 0;
        cntb0[i] = 0;
        cntb1[i] = 0;
    }
}

int getf_a(int x){
    if (faa[x] == x)
        return x;

    return faa[x] = getf_a(faa[x]);
}

int getf_b(int x){
    if (fab[x] == x)
        return x;

    return fab[x] = getf_b(fab[x]);
}

void merge_a(int x, int y){
    int fx = getf_a(x);
    int fy = getf_a(y);
    if (fx == fy)
        return;
    faa[fx] = fy;
    cnta0[fy] += cnta0[fx];
    cnta1[fy] += cnta1[fx];
}

void merge_b(int x, int y){
    int fx = getf_b(x);
    int fy = getf_b(y);
    if (fx == fy)
        return;
    fab[fx] = fy;
    cntb0[fy] += cntb0[fx];
    cntb1[fy] += cntb1[fx];
}

int main(){
    freopen("edit.in", "r", stdin);
    freopen("edit.out", "w", stdout);
    cin>>T;
    while (T--){
        cin>>n;
        init();
        for (int i = 1; i <= n; i++){
            cin>>a[i];
            a[i] -= '0';

            if (a[i]){
                cnta1[i] = 1;
            }else{
                cnta0[i] = 1;
            }
        }
        for (int i = 1; i <= n; i++){
            cin>>b[i];
            b[i] -= '0';

            if (b[i]){
                cntb1[i] = 1;
            }else{
                cntb0[i] = 1;
            }
        }
        for (int i = 1; i <= n; i++){
            cin>>t1[i];
            t1[i] -= '0';

            if (t1[i-1] && t1[i]){
                merge_a(i-1, i);
            }
        }
        for (int i = 1; i <= n; i++){
            cin>>t2[i];
            t2[i] -= '0';

            if (t2[i-1] && t2[i]){
                merge_b(i-1, i);
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++){
            int fa = getf_a(i);
            int fb = getf_b(i);

            if (cnta0[fa] && cntb0[fb]){
                cnta0[fa]--;
                cntb0[fb]--;
                ans++;
            }else if (cnta1[fa] && cntb1[fb]){
                cnta1[fa]--;
                cntb1[fb]--;
                ans++;
            }
        }
        printf("%d\n", ans);
    }


    return 0;
}

递交者: HI-0029
题目: NOIP2024A NOIP2024A
比赛: 【民间数据】NOIP2024 HI 批量测试
语言: C++14(O2)
代码长度: 2.7 KiB
递交时间: 2024-12-1 16:25:27
评测时间: 2024-12-1 16:28:39

分数: 100
总耗时: 954ms
峰值时间: 124ms
峰值内存: 4 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录