Submission #1131414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131414		vladilius	Collapse (JOI18_collapse)	C++20	0 / 100	15082 ms	5752 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<int> out(q);
    for (int i = 0; i < q; i++){
        p[i]++;
        dsu T; T.init(n);
        for (int j = 0; j <= w[i]; j++){
            if (max(x[j], y[j]) <= p[i]){
                T.unite(x[j], y[j]);
            }
        }
        out[i] += (T.cc - (n - p[i]));
        T.complete();
        for (int j = 0; j <= w[i]; j++){
            if (min(x[j], y[j]) > p[i]){
                T.unite(x[j], y[j]);
            }
        }
        out[i] += (T.cc - p[i]);
    }
    return out;
}

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