【警示后人】离散化的数组要开多大

我的离散化方法看上去很奇怪。但是这段代码让我得了 90 分，只有最后一个点 RE了。

经过排查，RE 的原因是 constexpr int maxn=1e5+10; 这里数组开小了。尽管题目中

1\le n\le10^5

，但假设每次询问都是两个不同的数字（比如

n=2

，那么可以出现

(1,2),(3,4)

这样，4种数字组合），于是被离散化的数字的总可能性上限应该是

2n

。

CPP

#include <stdio.h>
#include <stdlib.h>
#include <unordered_map>
#include <assert.h>

std::unordered_map<int, int> mp;

constexpr int maxn=1e5+10;

int a[maxn];

int read(){
    int ans=0;
    char c;
    while (c=getchar()){
        if (c>='0'&&c<='9'){
            ans = c-'0';
            break;
        }
    }
    while (c=getchar()){
        if (c>='0'&&c<='9'){
            ans *= 10;
            ans += c-'0';
        } else {
            return ans;
        }
    }
    return ans;
}

void clear(){
    for (int i=0; i<maxn; i++){
        a[i] = i;
    }
    mp.clear();
}

int get_fa(int n){
    if (a[n]==n)    return n;
    else    return a[n]=get_fa(a[n]);
}

void merge(int x, int y){
    int aa=get_fa(x), bb=get_fa(y);
    a[bb] = aa;
}

int ms[maxn][2];
int cnt=0;



int main(){
    int t;
    scanf("%d", &t);

    while (t--){
        int n;
        cnt = 0;
        scanf("%d", &n);
        clear();
        while (n--){        
            int i, j, e;
            // scanf("%d%d%d", &i, &j, &e);
            i = read(), j=read(), e=read();
            if (mp[i]==0){
                mp[i] = mp.size()+1;
            } 
            i = mp[i];
            if (mp[j]==0){
                mp[j] = mp.size()+1;
            }
            j = mp[j];
            if (e==1){
                merge(i, j);
            } else {
                ms[cnt][0] = i;
                ms[cnt][1] = j;
                cnt++;
            }
        }
        bool ok = true;
        for (int i=0; i<cnt; i++){
            if (get_fa(ms[i][0])==get_fa(ms[i][1])){
                ok = false;
                break;
            }
        }  
        // printf("%d\n", mp.size());

        if (ok){
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

【警示后人】离散化的数组要开多大

讨论操作

回复

相关推荐

【警示后人】离散化的数组要开多大