求助,未知原因 TLE
查看原帖
求助,未知原因 TLE
19905
DarkMoon_Dragon楼主2022/7/15 00:22

如题,未查明原因TLE QAQ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
const int N = 3e5;
int fa[N];
long long a[N];
vector<int> seg[N];

int find(int x) {
    return (fa[x] == x ? fa[x] : fa[x] = find(fa[x]));
}

void solve() {
    int n, m, l, r;
    long long x;
    scanf("%d%d", &n, &m);
    fa[0] = a[0] = 0;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        scanf("%lld", &a[i]);
    }
    fa[n + 1] = n + 1;
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &x);
        a[i] += a[i - 1]  - x;
    }
    for (int i = 0; i <= n; ++i) {
        if (a[i] == 0) {
            fa[i] = i + 1;
            q.push(i);
        }
    }
    // a[i] => s[i]
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &l, &r);
        seg[l - 1].push_back(r);
        seg[r].push_back(l - 1);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : seg[u]) {
            if (a[v]) continue;
            l = min(v, u), r = max(v, u);
            int now = l;
            while (now <= r) {
                if (a[now] != 0) {
                    a[now] = 0;
                    q.push(now);
                }
                fa[now] = now = find(now + 1);
                //if (n == m && n == 200000) cout << now << endl;
            }
        }
    }
    bool pd = true;
    for (int i = 0; i <= n; ++i) {
        if (a[i] != 0)
            pd = false;
        seg[i].clear();
    }
    if (pd) puts("YES");
    else puts("NO");
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}
2022/7/15 00:22
加载中...