萌新TLE#58求助
  • 板块CF891C Envy
  • 楼主Z1qqurat
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/1 18:24
  • 上次更新2023/11/3 06:30:45
查看原帖
萌新TLE#58求助
483928
Z1qqurat楼主2023/8/1 18:24

找了一圈没有跟我错的一样的,求调

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#define ll long long
#define pii pair<int, int>
#define mr make_pair
using namespace std;
const int N = 5e5 + 5;
int n, m, q, val[N], lim;
vector <int> e[N], tmp;
vector <vector<int> > gr[N];
vector <bool> ans[N];
struct Edge{
    int u, v, w;
}ed[N];
vector <pii> qr[N];
int vis[N];

struct DSU{
    int fa[N], siz[N];
    stack <int> opt;
    void init() {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i, siz[i] = 1;
        }
        return ;
    }
    int getroot(int x) {
        if(fa[x] == x) return x;
        return getroot(fa[x]);
    }
    void merge(int x, int y) {
        x = getroot(x), y = getroot(y);
        if(x == y) return ;
        if(siz[x] > siz[y]) swap(x, y);
        siz[y] += siz[x], fa[x] = y;
        opt.push(x); return ;
    }
    void undo() {
        if(opt.empty()) return ;
        int u = opt.top(); opt.pop();
        siz[fa[u]] -= siz[u], fa[u] = u;
        return ;
    }
    void del(int cnt) {
        while(opt.size() > cnt) undo();
        return ;
    }
}rinne;

void MST(int w) {
    for (int i = 0; i < gr[w].size(); ++i) {
        vector <int> a = gr[w][i];
        /*cout << w << " : ";
        for (int j = 0; j < a.size(); ++j) {
            cout << a[j] << ' ';
        }
        cout << "->";*/
        int cnt = rinne.opt.size();
        for (int j = 0; j < a.size(); ++j) {
            int u = ed[a[j]].u, v = ed[a[j]].v;
            u = rinne.getroot(u), v = rinne.getroot(v);
            if(u == v) {
                ans[w][i] = 0; break;
            }
            rinne.merge(u, v);
        }
        // cout << ans[w][i] << "\n";
        rinne.del(cnt);
    }
    for (int i = 0; i < e[w].size(); ++i) {
        int u = ed[e[w][i]].u, v = ed[e[w][i]].v;
        if(u == v) continue;
        rinne.merge(u, v);
    }
    return ;
}

void offline() {
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i) {
        memset(vis, -1, sizeof(vis));
        int num; scanf("%d", &num);
        while(num--) {
            int a; scanf("%d", &a);
            int w = ed[a].w;
            if(vis[w] == -1) {
                vis[w] = gr[w].size();
                vector <int> b;
                gr[w].push_back(b);
                ans[w].push_back(1);
                qr[i].push_back(mr(w, vis[w]));
            }
            gr[w][vis[w]].push_back(a);
        }
        /*for (int j = 0; j <= n; ++j) {
            if(vis[j] != -1) {

            }
        }*/
    }
    return ;
}

void getans() {
    for (int i = 1; i <= lim; ++i) MST(i);
    for (int i = 1; i <= q; ++i) {
        bool bl = 1;
        for (int j = 0; j < qr[i].size(); ++j) {
            int w = qr[i][j].first, id = qr[i][j].second;
            if(!ans[w][id]) {
                bl = 0; break;
            }
        }
        if(bl) puts("YES");
        else puts("NO");
    }
    return ;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d %d", &ed[i].u, &ed[i].v, &ed[i].w);
        e[ed[i].w].push_back(i);
        lim = max(lim, ed[i].w);
    }
    rinne.init();
    offline();
    getans();
    return 0;
}
2023/8/1 18:24
加载中...