oj.uz

Submission #255934

# Submission time Handle Problem Language Result Execution time Memory
255934 2020-08-02T06:04:48 Z IgorI Collapse (JOI18_collapse) C++17
100 / 100
 11858 ms 40724 KB 
#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 = 2600;

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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15232 KB Output is correct
2 Correct 11 ms 14848 KB Output is correct
3 Correct 17 ms 14848 KB Output is correct
4 Correct 12 ms 14936 KB Output is correct
5 Correct 23 ms 15232 KB Output is correct
6 Correct 63 ms 15704 KB Output is correct
7 Correct 33 ms 14976 KB Output is correct
8 Correct 32 ms 14976 KB Output is correct
9 Correct 128 ms 15360 KB Output is correct
10 Correct 94 ms 15480 KB Output is correct
11 Correct 154 ms 15764 KB Output is correct
12 Correct 120 ms 15872 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21040 KB Output is correct
2 Correct 59 ms 20972 KB Output is correct
3 Correct 166 ms 28800 KB Output is correct
4 Correct 76 ms 20972 KB Output is correct
5 Correct 374 ms 28912 KB Output is correct
6 Correct 909 ms 22656 KB Output is correct
7 Correct 1151 ms 40180 KB Output is correct
8 Correct 842 ms 29392 KB Output is correct
9 Correct 8366 ms 22720 KB Output is correct
10 Correct 8197 ms 22772 KB Output is correct
11 Correct 10017 ms 23028 KB Output is correct
12 Correct 1934 ms 31752 KB Output is correct
13 Correct 5554 ms 34948 KB Output is correct
14 Correct 5814 ms 39668 KB Output is correct
15 Correct 4440 ms 39180 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 20972 KB Output is correct
2 Correct 55 ms 20972 KB Output is correct
3 Correct 63 ms 21100 KB Output is correct
4 Correct 70 ms 21100 KB Output is correct
5 Correct 278 ms 21232 KB Output is correct
6 Correct 774 ms 20532 KB Output is correct
7 Correct 3411 ms 32920 KB Output is correct
8 Correct 6618 ms 38716 KB Output is correct
9 Correct 8548 ms 22896 KB Output is correct
10 Correct 11497 ms 22896 KB Output is correct
11 Correct 7547 ms 40048 KB Output is correct
12 Correct 10722 ms 40712 KB Output is correct
13 Correct 8114 ms 39912 KB Output is correct
14 Correct 11048 ms 40296 KB Output is correct
15 Correct 7848 ms 39948 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15232 KB Output is correct
2 Correct 11 ms 14848 KB Output is correct
3 Correct 17 ms 14848 KB Output is correct
4 Correct 12 ms 14936 KB Output is correct
5 Correct 23 ms 15232 KB Output is correct
6 Correct 63 ms 15704 KB Output is correct
7 Correct 33 ms 14976 KB Output is correct
8 Correct 32 ms 14976 KB Output is correct
9 Correct 128 ms 15360 KB Output is correct
10 Correct 94 ms 15480 KB Output is correct
11 Correct 154 ms 15764 KB Output is correct
12 Correct 120 ms 15872 KB Output is correct
13 Correct 65 ms 21040 KB Output is correct
14 Correct 59 ms 20972 KB Output is correct
15 Correct 166 ms 28800 KB Output is correct
16 Correct 76 ms 20972 KB Output is correct
17 Correct 374 ms 28912 KB Output is correct
18 Correct 909 ms 22656 KB Output is correct
19 Correct 1151 ms 40180 KB Output is correct
20 Correct 842 ms 29392 KB Output is correct
21 Correct 8366 ms 22720 KB Output is correct
22 Correct 8197 ms 22772 KB Output is correct
23 Correct 10017 ms 23028 KB Output is correct
24 Correct 1934 ms 31752 KB Output is correct
25 Correct 5554 ms 34948 KB Output is correct
26 Correct 5814 ms 39668 KB Output is correct
27 Correct 4440 ms 39180 KB Output is correct
28 Correct 44 ms 20972 KB Output is correct
29 Correct 55 ms 20972 KB Output is correct
30 Correct 63 ms 21100 KB Output is correct
31 Correct 70 ms 21100 KB Output is correct
32 Correct 278 ms 21232 KB Output is correct
33 Correct 774 ms 20532 KB Output is correct
34 Correct 3411 ms 32920 KB Output is correct
35 Correct 6618 ms 38716 KB Output is correct
36 Correct 8548 ms 22896 KB Output is correct
37 Correct 11497 ms 22896 KB Output is correct
38 Correct 7547 ms 40048 KB Output is correct
39 Correct 10722 ms 40712 KB Output is correct
40 Correct 8114 ms 39912 KB Output is correct
41 Correct 11048 ms 40296 KB Output is correct
42 Correct 7848 ms 39948 KB Output is correct
43 Correct 1045 ms 26168 KB Output is correct
44 Correct 5225 ms 37612 KB Output is correct
45 Correct 1373 ms 26436 KB Output is correct
46 Correct 6546 ms 38052 KB Output is correct
47 Correct 8658 ms 22512 KB Output is correct
48 Correct 8503 ms 22540 KB Output is correct
49 Correct 11858 ms 22620 KB Output is correct
50 Correct 6446 ms 21624 KB Output is correct
51 Correct 3022 ms 27940 KB Output is correct
52 Correct 4514 ms 30568 KB Output is correct
53 Correct 3723 ms 30236 KB Output is correct
54 Correct 5952 ms 33084 KB Output is correct
55 Correct 5571 ms 32732 KB Output is correct
56 Correct 6054 ms 35184 KB Output is correct
57 Correct 6831 ms 37460 KB Output is correct
58 Correct 9253 ms 37948 KB Output is correct
59 Correct 7025 ms 40012 KB Output is correct
60 Correct 10895 ms 40724 KB Output is correct