Submission #92334

#	Time	Username	Problem	Language	Result	Execution time	Memory
92334		Alexa2001	Collapse (JOI18_collapse)	C++17	100 / 100	4046 ms	30684 KiB

collapse

#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

const int Bsize = 323, Nmax = 1e5 + 5;

struct Edge
{
    int x, y, t1, t2;
    bool operator < (const Edge &other) const
    {
        return y < other.y;
    }
};
struct Query
{
    int pos, t, id;
    bool operator < (const Query &other) const
    {
        return pos < other.pos;
    }
};
vector<int> answer;
vector<Query> queries;
vector<Edge> edges;
map< pair<int,int> , int > mp;
int N, Q, M;

namespace forest
{
    static int moves;
    static int t[Nmax], rang[Nmax];
    static vector<int> S, T;

    void init()
    {
        moves = 0;
        S.clear(); T.clear();
        int i;
        for(i=0; i<N; ++i) t[i] = i;
    }

    int boss(int node)
    {
        while(t[node] != node) node = t[node];
        return node;
    }

    bool unite(int x, int y)
    {
        x = boss(x); y = boss(y);
        if(x == y) return 0;

        ++moves;

        if(rang[x] == rang[y])
        {
            ++rang[y];
            S.push_back(y);
        }
        else
        {
            S.push_back(0);
            if(rang[x] > rang[y]) swap(x, y);
        }
        t[x] = y;
        T.push_back(x);
        return 1;
    }

    void undo(int nr)
    {
        moves -= nr;
        while(nr--)
        {
            assert(S.size());
            assert(T.size());

            int x, y;
            x = T.back(), y = S.back();
            S.pop_back(); T.pop_back();
            t[x] = x;
            if(y) rang[y] --;
        }
    }
}

void solve(vector<Edge> E, vector<Query> Q)
{
    int i;
    vector<Query> v[Nmax];
    vector<Edge> all, possible;

    for(auto it : Q)
        v[it.t / Bsize * Bsize].push_back(it);

    for(i=0; i<=M; i += Bsize) if(!v[i].empty())
    {
        forest::init();
        all.clear();
        possible.clear();

        for(auto it : E)
            if(it.t1 <= i && it.t2 >= i + Bsize - 1) all.push_back(it);
                else if(it.t2 >= i && it.t1 <= i + Bsize - 1) possible.push_back(it);

        sort(all.begin(), all.end());
        sort(v[i].begin(), v[i].end());

        int cursor = 0;
        for(auto q : v[i])
        {
            while(cursor < all.size() && all[cursor].y <= q.pos)
                forest::unite(all[cursor].x, all[cursor].y), ++cursor;

            int undo = 0;
            for(auto it : possible)
                if(it.t1 <= q.t && q.t <= it.t2 && it.y <= q.pos)
                    if(forest::unite(it.x, it.y)) ++undo;

            answer[q.id] -= forest::moves;
            forest::undo(undo);
        }
    }
}

vector<int> simulateCollapse (int _N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
    N = _N, M = T.size(), Q = W.size();
    int i;
    answer.resize(Q);
    for(i=0; i<Q; ++i) answer[i] = N;

    for(i=0; i<M; ++i)
    {
        if(X[i] > Y[i]) swap(X[i], Y[i]);
        if(T[i] == 0) mp[{X[i], Y[i]}] = i;
            else
            {
                edges.push_back({X[i], Y[i], mp[{X[i], Y[i]}], i - 1});
                mp[{X[i], Y[i]}] = -1;
            }
    }

    for(auto it : mp)
        if(it.second != -1)
            edges.push_back({it.first.first, it.first.second, it.second, M-1});

    for(i=0; i<Q; ++i)
        queries.push_back({P[i], W[i], i});

    solve(edges, queries);

    for(auto &it : edges)
    {
        it.x = N - it.x - 1, it.y = N - it.y - 1;
        swap(it.x, it.y);
    }

    for(auto &it : queries)
        it.pos = N - it.pos - 2;

    solve(edges, queries);

    return answer;
}

Compilation message (stderr)

collapse.cpp: In function 'void solve(std::vector<Edge>, std::vector<Query>)':
collapse.cpp:114:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(cursor < all.size() && all[cursor].y <= q.pos)
                   ~~~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35