oj.uz

Submission #940073

# Submission time Handle Problem Language Result Execution time Memory
940073 2024-03-07T05:04:04 Z vjudge1 Collapse (JOI18_collapse) C++17
30 / 100
 213 ms 45516 KB 
#include "collapse.h"
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <utility>

#define S 400
#define N 100000

struct dsu
{
    std::vector<int>p;
    std::stack<std::pair<int, int> > save;

    dsu() {}
    dsu(int n): p(n, -1), savemode(0), comp(n) {}
    int savemode, comp;

    int find(int x) { return p[x] < 0 ? x : find(p[x]); }

    bool unite(int x, int y)
    {
        if ((x = find(x)) == (y = find(y))) return false;
        if (-p[x] < -p[y]) std::swap(x, y);
        save.push(std::make_pair(y, p[y]));
        p[x] += p[y];
        p[y] = x;
        --comp;
        return true;
    }

    void rollback()
    {
        auto [y, py] = save.top();
        save.pop();
        int x = p[y];
        p[x] -= py;
        p[y] = py;
        ++comp;
    }
};

int n, c, q;
std::vector<std::pair<int, int> > t[N<<2];
std::vector<std::pair<int, int > > at[N];
std::vector<int> ans;

dsu ds[999];

void ins(int v, int l, int r, int x, int y, int ex, int ey)
{
    if (r < x || y < l) return;
    if (x <= l && r <= y)
    {
        t[v].emplace_back(ex, ey);
        return;
    }
    ins(2*v+1, l, (l+r)/2, x, y, ex, ey);
    ins(2*v+2, (l+r)/2+1, r, x, y, ex, ey);
}

int ban;

dsu ds1;

void dfs(int v, int l, int r)
{
    //printf("%d %d %d\n",v,l,r);fflush(stdout);
    int nrb = 0;
    for (auto[x,y]:t[v])
    {
        if (x <= ban && ban < y) continue;
        nrb += ds1.unite(x, y);
    }

    if (l-r) dfs(2*v+1,l,(l+r)/2),dfs(2*v+2,(l+r)/2+1,r);
    else
    {
        for (auto[i,_]:at[l])
        {
            ans[i] = ds1.comp;
        }
    }

    while (nrb--) ds1.rollback();
}

std::vector<int> simulateCollapse(
	int n0,
	std::vector<int> t,
	std::vector<int> x,
	std::vector<int> y,
	std::vector<int> w,
	std::vector<int> p
) {
    n=n0;c=t.size();q=w.size();

    ban = p[0];

    {
        std::map<std::pair<int, int>, int> st;
        for (int i = 0; i < t.size(); ++i)
        {
            if(x[i] > y[i]) std::swap(x[i], y[i]);

            if (t[i] == 0)
            {
                st[std::make_pair(x[i], y[i])] = i;
            }
            else
            {
                ins(0, 0, c, st[std::make_pair(x[i], y[i])], i - 1, x[i], y[i]);
                st.erase(std::make_pair(x[i], y[i]));
            }
        }
        for (auto [xy, in] : st)
            ins(0, 0, c, in, c-1, xy.first, xy.second);
    }

    //for (int i = 0; i < S; ++i) ds[i] = S;

    ds1 = dsu(n);
    ds1.savemode = 1;

    for (int i = 0; i < q; ++i)
        at[w[i]].emplace_back(i, p[i]);

    ans.resize(q);
    dfs(0, 0, c);

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13148 KB Output is correct
2 Incorrect 4 ms 12884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15828 KB Output is correct
2 Correct 22 ms 16856 KB Output is correct
3 Correct 86 ms 26536 KB Output is correct
4 Correct 26 ms 16984 KB Output is correct
5 Correct 96 ms 28240 KB Output is correct
6 Correct 33 ms 18524 KB Output is correct
7 Correct 181 ms 44916 KB Output is correct
8 Correct 103 ms 29008 KB Output is correct
9 Correct 25 ms 17108 KB Output is correct
10 Correct 24 ms 17236 KB Output is correct
11 Correct 29 ms 18256 KB Output is correct
12 Correct 109 ms 29516 KB Output is correct
13 Correct 170 ms 38000 KB Output is correct
14 Correct 213 ms 45496 KB Output is correct
15 Correct 187 ms 45516 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15828 KB Output is correct
2 Incorrect 22 ms 16472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13148 KB Output is correct
2 Incorrect 4 ms 12884 KB Output isn't correct
3 Halted 0 ms 0 KB -