oj.uz

Submission #363275

# Submission time Handle Problem Language Result Execution time Memory
363275 2021-02-05T12:22:05 Z buyolitsez Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 15196 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 == 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());
    }
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 748 KB Output is correct
2 Correct 18 ms 492 KB Output is correct
3 Correct 18 ms 620 KB Output is correct
4 Correct 19 ms 620 KB Output is correct
5 Correct 32 ms 748 KB Output is correct
6 Correct 159 ms 1132 KB Output is correct
7 Correct 18 ms 620 KB Output is correct
8 Correct 18 ms 620 KB Output is correct
9 Correct 32 ms 876 KB Output is correct
10 Correct 83 ms 1004 KB Output is correct
11 Correct 236 ms 1192 KB Output is correct
12 Correct 186 ms 1180 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 3564 KB Output is correct
2 Correct 362 ms 3564 KB Output is correct
3 Correct 4679 ms 8064 KB Output is correct
4 Correct 404 ms 3948 KB Output is correct
5 Correct 4934 ms 8336 KB Output is correct
6 Correct 2561 ms 5016 KB Output is correct
7 Execution timed out 15086 ms 15196 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 3436 KB Output is correct
2 Correct 339 ms 3564 KB Output is correct
3 Correct 369 ms 4076 KB Output is correct
4 Correct 354 ms 3948 KB Output is correct
5 Correct 734 ms 4276 KB Output is correct
6 Correct 2684 ms 4988 KB Output is correct
7 Execution timed out 15093 ms 12644 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 748 KB Output is correct
2 Correct 18 ms 492 KB Output is correct
3 Correct 18 ms 620 KB Output is correct
4 Correct 19 ms 620 KB Output is correct
5 Correct 32 ms 748 KB Output is correct
6 Correct 159 ms 1132 KB Output is correct
7 Correct 18 ms 620 KB Output is correct
8 Correct 18 ms 620 KB Output is correct
9 Correct 32 ms 876 KB Output is correct
10 Correct 83 ms 1004 KB Output is correct
11 Correct 236 ms 1192 KB Output is correct
12 Correct 186 ms 1180 KB Output is correct
13 Correct 340 ms 3564 KB Output is correct
14 Correct 362 ms 3564 KB Output is correct
15 Correct 4679 ms 8064 KB Output is correct
16 Correct 404 ms 3948 KB Output is correct
17 Correct 4934 ms 8336 KB Output is correct
18 Correct 2561 ms 5016 KB Output is correct
19 Execution timed out 15086 ms 15196 KB Time limit exceeded
20 Halted 0 ms 0 KB -