oj.uz

Submission #363273

# Submission time Handle Problem Language Result Execution time Memory
363273 2021-02-05T12:21:03 Z buyolitsez Collapse (JOI18_collapse) C++17
0 / 100
 351 ms 3564 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 748 KB Output is correct
2 Incorrect 18 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 3564 KB Output is correct
2 Incorrect 342 ms 3436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 3436 KB Output is correct
2 Incorrect 346 ms 3564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 748 KB Output is correct
2 Incorrect 18 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -