这段代码在codeforces上提交会超时
查看原帖
这段代码在codeforces上提交会超时
680697
lv__sc楼主2023/1/24 01:48
//
// Created by lv_shen on 2023/1/23.
//


#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
vector<int> c[100003];
int n;
//int cnt[N] = {0};

void solve()
{
    cin >> n;
    int cnt[N]={0};//会超时
    //memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++)
    {
        c[i].clear();
        int k;
        cin >> k;
        for (int j = 0; j < k; j++)
        {
            int p;
            cin >> p;
            c[i].emplace_back(p);
            cnt[p]++;
        }
    }
    bool f = false;
    for (int i = 0; i < n; i++)
    {
        bool f1 = true;
        for (auto x: c[i])
        {
            if (cnt[x] == 1)
            {
                f1 = false;
                break;
            }
        }
        if (f1)
        {
            f = true;
            break;
        }
    }
    if (f) cout << "YES\n";
    else cout << "NO\n";

//    for (int i = 0; i < n; i++)
//        for (auto x: c[i])
//            cnt[x]--;

}


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

这段代码会超时,但是如果把cnt开成全局变量,然后每次都清空cnt数组,就不会超时。是什么原因,难道说是开一个1e5的cnt数组会很耗时间吗

2023/1/24 01:48
加载中...