oj.uz

답안 #363265

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363265 2021-02-05T12:00:47 Z buyolitsez Collapse (JOI18_collapse) C++17
0 / 100
 8015 ms 4680 KB 
#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 (y < l || x > r) {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 (x <= m) {
                edgesL.emplace_back(a, b, x, y);
            }
            if (y <= r) {
                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 == 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;
        }
//        assert(need == p);
        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;
    }
//    Func(0, T.size(), edges, querys);
    return ans;
}

Compilation message

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:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < T.size(); ++i) {
      |                     ~~^~~~~~~~~~
collapse.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < W.size(); ++i) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 1544 KB Output is correct
2 Incorrect 405 ms 1260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8015 ms 4680 KB Output is correct
2 Incorrect 7984 ms 4680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7915 ms 4680 KB Output is correct
2 Incorrect 7924 ms 4680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 1544 KB Output is correct
2 Incorrect 405 ms 1260 KB Output isn't correct
3 Halted 0 ms 0 KB -