Submission #363277

#	Time	Username	Problem	Language	Result	Execution time	Memory
363277		buyolitsez	Collapse (JOI18_collapse)	C++17	30 / 100	282 ms	27484 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 15;
int p[MAXN];
int rang[MAXN];
vector <int> ans;
int need = -1;
int cntComp;

int GetPar(int v) {
    if (p[v] == -1) {
        return v;
    }
    return GetPar(p[v]);
}

void Comeback(int wasCnt, vector <tuple <int, int, int>> wasDSU) {
    reverse(wasDSU.begin(), wasDSU.end());
    cntComp = wasCnt;
    for (auto [a, b, c] : wasDSU) {
        p[a] = b;
        rang[a] = c;
    }
}

void Func(int l, int r, vector <tuple <int, int, int, int>> edges, vector <pair <int, int>> querys) {
    int m = l + (r - l) / 2;
    vector <tuple <int, int, int, int>> edgesL, edgesR;
    vector <pair <int, int>> querysL, querysR;
    vector <tuple <int, int, int>> wasDSU;
    int wasCnt = cntComp;
    for (auto [a, b, x, y] : edges) {
        if (min(a, b) <= need && max(a, b) >= need + 1) {continue;}
        if (x <= l && r <= y) {
            a = GetPar(a);
            b = GetPar(b);
            if (a == b) {continue;}
            wasDSU.emplace_back(a, p[a], rang[a]);
            wasDSU.emplace_back(b, p[b], rang[b]);
            if (rang[a] > rang[b]) {swap(a, b);}
            --cntComp;
            rang[b] += rang[a];
            p[a] = b;
        } else {
            if (!(y < l || x > m)) {
                edgesL.emplace_back(a, b, x, y);
            }
            if (!(m + 1 > y || r < x)) {
                edgesR.emplace_back(a, b, x, y);
            }
        }
    }
    if (l == r) {
        for (auto [pos, num] : querys) {
            ans[num] = cntComp;
        }
        Comeback(wasCnt, wasDSU);
        return;
    }
    for (auto [pos, num] : querys) {
        if (pos <= m) {
            querysL.emplace_back(pos, num);
        } else {
            querysR.emplace_back(pos, num);
        }
    }
    Func(l, m, edgesL, querysL);
    Func(m + 1, r, edgesR, querysR);
    Comeback(wasCnt, wasDSU);
}

std::vector<int> simulateCollapse( int N, std::vector<int> T, std::vector<int> X, std::vector<int> Y, std::vector<int> W, std::vector<int> P) {
    memset(p, -1, sizeof(p));
    fill(rang, rang + MAXN, 1);
    cntComp = N;
    vector <tuple <int, int, int, int>> edges;
    map <pair <int, int>, int> last;
    ans.resize(W.size(), -1);
    for (int i = 0; i < T.size(); ++i) {
        int type = T[i], a = X[i], b = Y[i];
        if (type == 0) {
            last[{min(a, b), max(a, b)}] = i;
        } else {
            edges.emplace_back(a, b, last[{min(a, b), max(a, b)}], i - 1);
            last.erase(last.find({min(a, b), max(a, b)}));
        }
    }
    for (auto [x, y] : last) {
        edges.emplace_back(x.first, x.second, y, T.size() - 1);
    }
    vector <pair <int, int>> querys(W.size());
    for (int i = 0; i < W.size(); ++i) {
        int w = W[i], p = P[i];
        if (need == -1) {
            need = p;
        }
        assert(need == p);
        querys[i] = {w, i};
    }
    Func(0, T.size() - 1, edges, querys);
    return ans;
}

Compilation message (stderr)

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 0; i < T.size(); ++i) {
      |                     ~~^~~~~~~~~~
collapse.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < W.size(); ++i) {
      |                     ~~^~~~~~~~~~

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