oj.uz

Submission #940118

# Submission time Handle Problem Language Result Execution time Memory
940118 2024-03-07T05:46:25 Z sleepntsheep Collapse (JOI18_collapse) C++17
30 / 100
 218 ms 45624 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 6 ms 13404 KB Output is correct
2 Incorrect 4 ms 12932 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 16336 KB Output is correct
2 Correct 22 ms 16732 KB Output is correct
3 Correct 117 ms 26580 KB Output is correct
4 Correct 22 ms 16952 KB Output is correct
5 Correct 100 ms 28240 KB Output is correct
6 Correct 29 ms 18500 KB Output is correct
7 Correct 200 ms 45020 KB Output is correct
8 Correct 102 ms 28936 KB Output is correct
9 Correct 24 ms 17088 KB Output is correct
10 Correct 24 ms 17348 KB Output is correct
11 Correct 27 ms 18144 KB Output is correct
12 Correct 100 ms 29456 KB Output is correct
13 Correct 161 ms 37748 KB Output is correct
14 Correct 218 ms 45400 KB Output is correct
15 Correct 216 ms 45624 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16340 KB Output is correct
2 Incorrect 21 ms 16468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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