Submission #255935

#	Time	Username	Problem	Language	Result	Execution time	Memory
255935		IgorI	Collapse (JOI18_collapse)	C++17	100 / 100	12656 ms	40800 KiB

collapse

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;

const int N = 302020;

int n;

int cuts[N];
int cutssz;
int root[N], sz[N];
int comp;

void Reset()
{
    for (int i = 0; i < n; i++) root[i] = i, sz[i] = 1;
    cutssz = 0;
    comp = n;
}

int Root(int x)
{
    if (x == root[x]) return root[x];
    return Root(root[x]);
}

void Merge(int v, int u)
{
    v = Root(v), u = Root(u);
    if (v == u) return;
    comp--;
    if (sz[v] < sz[u])
    {
        cuts[cutssz++] = v;
        sz[u] += sz[v];
        root[v] = u;
    }
    else
    {
        cuts[cutssz++] = u;
        sz[v] += sz[u];
        root[u] = v;
    }
}

void Cut()
{
    cutssz--;
    int x = cuts[cutssz];
    sz[root[x]] -= sz[x];
    root[x] = x;
    comp++;
}

int v[N], u[N], L[N], R[N], ans[N], z[N], it[N];

vector<pair<int, pair<int, int> > > on_left[N];
vector<pair<int, pair<int, int> > > on_right[N];

void solve(int le, int ri, int gap_le, int gap_ri)
{
    if (le + 1 == ri)
    {
        if (v[le] == -1)
        {
            int ss = cutssz;
            for (int i = gap_le + 1; i <= z[le]; i++)
            {
                for (auto e : on_left[i])
                {
                    if (e.second.first <= it[le] && it[le] < e.second.second)
                    {
                        Merge(e.first, i);
                    }
                }
            }
            for (int i = gap_ri - 1; i > z[le]; i--)
            {
                for (auto e : on_right[i])
                {
                    if (e.second.first <= it[le] && it[le] < e.second.second)
                    {
                        Merge(i, e.first);
                    }
                }
            }
            ans[le] = comp;
            while (cutssz != ss) Cut();
        }
        return;
    }
    int mi = (le + ri) / 2;
    int ss = cutssz;
    for (int i = le; i < mi; i++)
    {
        if (v[i] != -1 && R[i] != -1 && ri <= R[i]) Merge(v[i], u[i]);
    }
    solve(mi, ri, gap_le, gap_ri);
    while (cutssz != ss) Cut();
    for (int i = ri - 1; i >= mi; i--)
    {
        if (v[i] != -1 && L[i] != -1 && L[i] < le) Merge(v[i], u[i]);
    }
    solve(le, mi, gap_le, gap_ri);
    while (cutssz != ss) Cut();
}

void DCP(vector<int> x, vector<int> y, vector<pair<int, int> > &t, vector<int> p, int gap_le, int gap_ri)
{
    Reset();
    map<pair<int, int>, int> open;
    int T = 0;
    int j = 0;
    for (int i = 0; i < x.size(); i++)
    {
        if (y[i] <= gap_le || gap_ri <= x[i])
        {
            if (open.find({x[i], y[i]}) == open.end())
            {
                open[{x[i], y[i]}] = T;
                v[T] = x[i];
                u[T] = y[i];
                T++;
            }
            else
            {
                int z = open[{x[i], y[i]}];
                L[T] = z;
                L[z] = -1;
                R[T] = -1;
                R[z] = T;
                v[T] = x[i];
                u[T] = y[i];
                open.erase({x[i], y[i]});
                T++;
            }
        }
        while (j < t.size() && i == t[j].first)
        {
            v[T] = -1, u[T] = -1;
            it[T] = t[j].first;
            z[T] = p[j];
            T++;
            j++;
        }
    }
    solve(0, T, gap_le, gap_ri);
    j = 0;
    for (int i = 0; i < T; i++)
    {
        if (v[i] == -1)
        {
            t[j].first = ans[i];
            j++;
        }
    }
}

void solve_queries(int gap_le, int gap_ri, vector<int> x, vector<int> y, vector<int> w, vector<int> p, vector<int> &answer)
{
    vector<pair<int, int> > times;
    for (int i = 0; i < w.size(); i++)
    {
        if (gap_le <= p[i] && p[i] < gap_ri)
        {
            times.push_back({w[i], i});
        }
    }
    sort(times.begin(), times.end());
    vector<int> mp(times.size());
    for (int i = 0; i < times.size(); i++)
    {
        mp[i] = p[times[i].second];
    }
    if (times.size())
    DCP(x, y, times, mp, gap_le, gap_ri);
    for (int i = 0; i < times.size(); i++)
    {
        answer[times[i].second] = times[i].first;
    }
}

const int K = 3000;

vector<int> simulateCollapse(int n0, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p)
{
    n = n0;
    int c = t.size();
    int q = w.size();
    set<pair<int, int> > s;
    for (int i = 0; i < c; i++)
    {
        if (x[i] > y[i]) swap(x[i], y[i]);
        if (s.find({x[i], y[i]}) == s.end())
        {
            s.insert({x[i], y[i]});
        }
        else
        {
            s.erase({x[i], y[i]});
        }
    }
    while (s.size())
    {
        pair<int, int> d = *(s.begin());
        s.erase(s.begin());
        x.push_back(d.first);
        y.push_back(d.second);
        c++;
    }
    map<pair<int, int>, int> mm;
    for (int i = 0; i < c; i++)
    {
        if (mm.find({x[i], y[i]}) == mm.end())
        {
            mm[{x[i], y[i]}] = i;
        }
        else
        {
            int z = mm[{x[i], y[i]}];
            mm.erase({x[i], y[i]});
            on_left[y[i]].push_back({x[i], {z, i}});
            on_right[x[i]].push_back({y[i], {z, i}});
        }
    }
    vector<int> answer(q);
    vector<int> pleft(n);
    vector<int> pright(n);
    for (int i = 1; i < n; i++)
    {
        pleft[i] = pleft[i - 1] + on_left[i].size();
    }
    for (int i = n - 2; i >= 0; i--)
    {
        pright[i] = pright[i + 1] + on_right[i].size();
    }
    vector<pair<int, int> > e;
    int GL = 0;
    while (GL != n - 1)
    {
        int okay = GL + 1;
        for (int HF = GL + 1; HF < n; HF++)
        {
            if (pleft[HF - 1] - pleft[GL] <= K && pright[GL + 1] - pright[HF] <= K)
                okay = HF;
        }
        e.push_back({GL, okay});
        GL = okay;
    }
    for (auto ee : e)
    {
        solve_queries(ee.first, ee.second, x, y, w, p, answer);
    }
    return answer;
}

Compilation message (stderr)

collapse.cpp: In function 'void DCP(std::vector<int>, std::vector<int>, std::vector<std::pair<int, int> >&, std::vector<int>, int, int)':
collapse.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size(); i++)
                     ~~^~~~~~~~~~
collapse.cpp:142:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < t.size() && i == t[j].first)
                ~~^~~~~~~~~~
collapse.cpp: In function 'void solve_queries(int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>&)':
collapse.cpp:166:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < w.size(); i++)
                     ~~^~~~~~~~~~
collapse.cpp:175:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < times.size(); i++)
                     ~~^~~~~~~~~~~~~~
collapse.cpp:181:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < times.size(); i++)
                     ~~^~~~~~~~~~~~~~

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