Submission #1131426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131426		vladilius	Collapse (JOI18_collapse)	C++20	30 / 100	4921 ms	302432 KiB

collapse

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct dsu{
    vector<int> sz, p, rem;
    int n, cc, cc1;
    void init(int ns){
        n = ns;
        sz.resize(n + 1);
        p.resize(n + 1);
        for (int i = 1; i <= n; i++){
            sz[i] = 1;
            p[i] = i;
        }
        cc = n;
        cc1 = 0;
    }
    int get(int v){
        if (v != p[v]){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y){
        rem.pb(x); rem.pb(y);
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
        cc--; cc1++;
    }
    void clear(){
        for (int i: rem){
            sz[i] = 1;
            p[i] = i;
        }
        rem.clear();
        cc1 = 0;
    }
    void complete(){
        for (int i = 1; i <= n; i++){
            sz[i] = 1;
            p[i] = i;
        }
        cc = n;
    }
};

vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p){
    int m = (int) t.size();
    for (int i = 0; i < m; i++){
        x[i]++; y[i]++;
    }
    int q = (int) w.size();
    vector<pii> qs[m];
    for (int i = 0; i < q; i++){
        p[i]++;
        qs[w[i]].pb({p[i], i});
    }
    
    const int S = min(m, 1000);
    
    vector<int> out(q);
    vector<int> c1(n + 1);
    for (int i = 0; i < m; i++){
        c1[max(x[i], y[i])]++;
        c1[min(x[i], y[i]) - 1]++;
    }
    vector<pii> f;
    int i = 1;
    while (i <= n){
        if (c1[i] >= S){
            f.pb({i, i});
            i++;
            continue;
        }
        int j = i, sum = 0;
        while (j <= n && sum < S){
            if (c1[j] >= S){
                j--;
                break;
            }
            sum += c1[j];
            j++;
        }
        f.pb({i, min(n, j)});
        i = j + 1;
    }

    int k = (int) f.size();
    
    dsu T[k];
    for (int i = 0; i < k; i++) T[i].init(n);
    
    vector<int> move(n + 2); move[n + 1] = n + 1;
    for (int i = n; i > 0; i--){
        if (c1[i]) move[i] = i;
        else move[i] = move[i + 1];
    }
    
    vector<pii> d[n + 1];
    dsu F; F.init(n);
    for (int i = 0; i < m; i++){
        int v = max(x[i], y[i]);
        for (int j = 0; j < k; j++){
            auto [l, r] = f[j];
            if (v <= l){
                T[j].unite(x[i], y[i]);
            }
        }
        d[v].pb({x[i], y[i]});
        
        for (auto [v, ii]: qs[i]){
            for (int j = 0; j < k; j++){
                auto [l, r] = f[j];
                if (l <= v && v <= r){
                    for (int s = l; s <= v; s++){
                        s = move[s];
                        if (s > v) break;
                        for (auto [u1, u2]: d[s]){
                            int v1 = T[j].get(u1);
                            int v2 = T[j].get(u2);
                            F.unite(v1, v2);
                        }
                    }
                    out[ii] += (T[j].cc - (n - v) - F.cc1);
                    F.clear();
                    break;
                }
            }
        }
    }
    
    for (int i = 0; i < k; i++) T[i].complete();
    for (int i = 1; i <= n; i++) d[i].clear();
    
    for (int i = 0; i < m; i++){
        int v = min(x[i], y[i]) - 1;
        for (int j = 0; j < k; j++){
            auto [l, r] = f[j];
            if (r <= v){
                T[j].unite(x[i], y[i]);
            }
        }
        d[v].pb({x[i], y[i]});
        
        for (auto [v, ii]: qs[i]){
            for (int j = 0; j < k; j++){
                auto [l, r] = f[j];
                if (l <= v && v <= r){
                    for (int s = v; s <= r; s++){
                        s = move[s];
                        if (s > r) break;
                        for (auto [u1, u2]: d[s]){
                            int v1 = T[j].get(u1);
                            int v2 = T[j].get(u2);
                            F.unite(v1, v2);
                        }
                    }
                    out[ii] += (T[j].cc - v - F.cc1);
                    F.clear();
                    break;
                }
            }
        }
    }
    return out;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 30 / 30
• Subtask 4: 0 / 35