Submission #363273

#	Time	Username	Problem	Language	Result	Execution time	Memory
363273		buyolitsez	Collapse (JOI18_collapse)	C++17	0 / 100	351 ms	3564 KiB

collapse

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

using namespace std;

const int MAXN = 5000 + 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]);
}

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) {
    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 == 1) {
            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());
    }
    vector <pair <int, int>> querys(W.size());
    for (int i = 0; i < W.size(); ++i) {
        int w = W[i], p1 = P[i];
        if (need == -1) {
            need = p1;
        }
        querys[i] = {w, i};
        memset(p, -1, sizeof(p));
        fill(rang, rang + MAXN, 1);
        cntComp = N;
        for (auto [a, b, x, y] : edges) {
            if (x > w || y < w) {continue;}
            if (min(a, b) <= p1 && max(a, b) >= p1 + 1) {continue;}
            a = GetPar(a);
            b = GetPar(b);
            if (a != b) {
                --cntComp;
                if (rang[a] > rang[b]) {
                    swap(a, b);
                }
                rang[b] += rang[a];
                p[a] = b;
            }
        }
        ans[i] = cntComp;
    }
    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:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < T.size(); ++i) {
      |                     ~~^~~~~~~~~~
collapse.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < W.size(); ++i) {
      |                     ~~^~~~~~~~~~

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