1 条题解

  • 2
    @ 2021-6-2 21:20:45

    题意:强制在线,求最小的 kk ,使得保留边权 k\leqslant k 的边集后 psps 所在连通块有不少于 ptpt 种颜色。

    30分暴力:二分这个权值 kk,暴力 dfsdfs 统计 psps 所在连通块内的颜色数目。

    复杂度是 O(qnlogw)\mathcal{O(qn \log w)}

    #include <cstdio>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #define rep(i,a,b) for(int i=(a);i<=(b);++i)
    #define per(i,a,b) for(int i=(a);i>=(b);--i)
    #define repp(i,a,b) for(int i=(a);i<(b);++i)
    #define perr(i,a,b) for(int i=(a);i>(b);--i)
    #define rii(x,y) ri(x), ri(y)
    #define riii(x,y,z) ri(x), ri(y), ri(z)
    #define rz resize
    #define pb push_back
    #define clr clear
    
    using namespace std;
    
    struct edge { int x, w; };
    vector< vector<edge> > g;
    vector< vector<int> > col;
    vector<int> buc, stk;
    
    int wt, v_col;
    
    
    inline void ri(int &x) {
        x = 0; char ch; int f = 1;
        do { ch = getchar(); if(ch == '-') f = -1; } while( ch < '0' || ch > '9');
        do { x = (x<<3) + (x<<1) + (ch&15), ch = getchar(); } while(ch >= '0' && ch <= '9');
        x *= f;
    }
    
    vector<int> vis;
    void dfs(int cur, int pre) {
        vis[cur] = v_col;
        for(int cl : col[cur]) buc[cl] = v_col;
        for(edge e : g[cur])
            if(vis[e.x] != v_col && e.w <= wt)
                dfs(e.x, cur);
    }
    
    int check(int n, int start, int weight) {
        wt = weight; ++v_col;
        dfs(start, 0);
        int ret = 0;
        for(int i : buc) if(i == v_col) ++ret;
        return ret;
    }
    
    int main() {
        int n, m, nums, a, u, v, w; rii(n, m);
        col.rz(n + 1); g.rz(n + 1);
        stk.pb(0);
        rep(i,1,n) {
            ri(nums); rep(j,1,nums) ri(a), col[i].pb(a);
        }
        rep(i,1,m) {
            riii(u, v, w);
            g[u].pb({v, w}); g[v].pb({u, w});
            stk.pb(w);
        }
        sort(stk.begin(), stk.end());
        vector<int>::iterator ed = unique(stk.begin(), stk.end());
        stk.erase(ed, stk.end());
        buc.assign(stk[stk.size()-1]+10, 0);
        vis.assign(n + 10, 0);
        int q, k; rii(q, k);
        int lastans = 0;
        rep(qr, 1, q) {
            int l = 0, r = stk.size() - 1, s, t;
            rii(s, t);
            s = (s ^ lastans) % n + 1, t = (t ^ lastans) % k + 1;
            if(check(n, s, stk[r]) < t) {
                puts("-1"); lastans = 0; continue;
            }
            while(l < r) {
                int mid = (l + r) >> 1;
                if(check(n, s, stk[mid]) >= t) r = mid;
                else l = mid + 1;
            }
            lastans = stk[l];
            printf("%d\n", stk[l]);
        }
        return 0;
    }
    
    

    100分做法:

    考虑优化统计颜色数的过程,保留 k\leqslant k 边集后的极大连通块显然是原图的 kruskal 重构树上所有点权小于等于 kk 且父节点不存在或者权值大于 kk 的结点。

    所以原题就等同于在 kruskal 重构树上寻找 psps 代表的叶节点的深度最浅的含有颜色数大于等于 ptpt 的子树的祖先,显然具有单调性用倍增来找。统计就转化成了在 dfs 序上数颜色数,用主席树维护一下就好了。

    复杂度为 O(qlog2n)\mathcal{O(q\log ^2 n)}

    #include <cstdio>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #define rep(i,a,b) for(int i=(a);i<=(b);++i)
    #define per(i,a,b) for(int i=(a);i>=(b);--i)
    #define repp(i,a,b) for(int i=(a);i<(b);++i)
    #define perr(i,a,b) for(int i=(a);i>(b);--i)
    #define rii(x, y) ri(x), ri(y)
    #define pb push_back
    #define rz resize
    #define clr clear
    using namespace std;
    
    typedef long long ll;
    typedef double db;
    typedef long double ldb;
    
    inline void ri(int &x) {
        x = 0; char ch; int f = 1;
        do { ch = getchar(); if(ch == '-') f = -1; } while( ch < '0' || ch > '9' );
        do { x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); } while( ch >= '0' && ch <= '9' );
        x *= f;
    }
    
    const int maxn = 1e5+10, maxm = 1e6+10, maxa = 1e5+10;
    
    struct edges_kr {int x, y, z;} es[maxm];
    vector<int> col[maxn];
    
    vector< vector<int> > krt;
    int fa[maxn<<1][25], par[maxn<<1], wt[maxn<<1];
    int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
    void krt_build(int n, int m) {
        sort( es + 1, es + m + 1, [&](edges_kr &a, edges_kr &b) { return a.z < b.z; } );
        rep(i,1,(n<<1)-1) par[i] = i, wt[i] = 0;
        krt.clr(); krt.rz(n << 1);
        int cnt = n;
        rep(i,1,m) {
            int x = find(es[i].x), y = find(es[i].y), z = es[i].z;
            if(x == y) continue;
            krt[++cnt].pb(x), krt[cnt].pb(y);
            wt[cnt] = z; fa[x][0] = fa[y][0] = par[x] = par[y] = cnt;
            if(cnt == (n<<1) - 1) break;
        }
    }
    
    int dfn[maxn<<1], idfn[maxn<<1], dep[maxn<<1], siz[maxn<<1], dfs_clock;
    void dfs(int cur) {
        dfn[cur] = ++dfs_clock; idfn[dfs_clock] = cur;
        dep[cur] = dep[fa[cur][0]] + 1; siz[cur] = 1;
        for(int i = 1; i < 23; ++i) fa[cur][i] = fa[fa[cur][i-1]][i-1];
        for(int ver : krt[cur]) dfs(ver), siz[cur] += siz[ver];
    }
    
    int rt[maxn<<1], ls[maxm*40], rs[maxm*40], dat[maxm*40], tot;
    void ist(int &p, int pre, int lp, int rp, int x, int v) {
        p = ++tot;
        if(lp == rp) { dat[p] = dat[pre] + v; return; }
        int mid = (lp + rp) >> 1;
        if(x <= mid) rs[p] = rs[pre], ist(ls[p], ls[pre], lp, mid, x, v);
        else ls[p] = ls[pre], ist(rs[p], rs[pre], mid+1, rp, x, v);
        dat[p] = dat[ls[p]] + dat[rs[p]];
    }
    
    int qry(int p, int lp, int rp, int x) {
        if(x <= lp) return dat[p];
        int mid = (lp + rp) >> 1;
        if(x <= mid) return qry(ls[p], lp, mid, x) + dat[rs[p]];
        return qry(rs[p], mid+1, rp, x);
    }
    
    int pre[maxa];
    
    int main() {
        int n, m, nums, a;
        rii(n, m);
        rep(i,1,n) {
            ri(nums);  rep(j,1,nums) ri(a), col[i].pb(a);
        }
        rep(i,1,m) {
            ri(es[i].x); ri(es[i].y); ri(es[i].z);
        }
        krt_build(n, m);
        dfs((n<<1)-1);
        rep(i,1,(n<<1)-1) {
            if(idfn[i] > n || col[idfn[i]].empty()) {
                rt[i] = rt[i-1]; continue;
            }
            ist(rt[i], rt[i-1], 1, (n<<1)-1, i, col[idfn[i]].size());
            for(int cl : col[idfn[i]]) {
                if(pre[cl]) ist(rt[i], rt[i], 1, (n<<1)-1, pre[cl], -1);
                pre[cl] = i;
            }
        }
        int sum = 0; rep(i,1,maxa-10) sum += (pre[i] != 0);
        int lastans = 0;
        int q, s, t, k;
        rii(q, k);
        rep(qr,1,q) {
            rii(s, t);
            s = (s ^ lastans) % n + 1, t = (t ^ lastans) % k + 1;
            if(col[s].size() >= t) {
                puts("0"); lastans = 0; continue;
            }
            if(t > sum) {
                puts("-1"); lastans = 0; continue;
            }
            per(i,23,0) {
                if(!fa[s][i]) continue;
                if(qry(rt[dfn[fa[s][i]]+siz[fa[s][i]]-1], 1, (n<<1)-1, dfn[fa[s][i]]) < t) s  = fa[s][i];
            }
            s = fa[s][0];
            printf("%d\n", wt[s]);
            lastans = wt[s];
        }
        return 0;
    }
    

    暴踩 std :
    用线段树合并 / set启发式合并能在单 log\log 预处理之后 O(1)\mathcal{O(1)} 查询,暴踩 std 。

    信息

    ID
    138
    时间
    1500ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    28
    已通过
    6
    上传者