oj.uz

Submission #255927

# Submission time Handle Problem Language Result Execution time Memory
255927 2020-08-02T05:54:29 Z IgorI Collapse (JOI18_collapse) C++17
35 / 100
 15000 ms 42928 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;

vector<int> cuts;
int root[N], sz[N];
int comp;

void Reset()
{
    for (int i = 0; i < n; i++) root[i] = i, sz[i] = 1;
    cuts.clear();
    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.push_back(v);
        sz[u] += sz[v];
        root[v] = u;
    }
    else
    {
        cuts.push_back(u);
        sz[v] += sz[u];
        root[u] = v;
    }
}

void Cut()
{
    int x = cuts.back();
    cuts.pop_back();
    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 = cuts.size();
            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 (cuts.size() != ss) Cut();
        }
        return;
    }
    int mi = (le + ri) / 2;
    int ss = cuts.size();
    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 (cuts.size() != 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 (cuts.size() != 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];
    }
    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 = 5000;

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;
    }
    assert(e.size() <= 40);
    for (auto ee : e)
    {
        solve_queries(ee.first, ee.second, x, y, w, p, answer);
    }
    return answer;
}

#ifdef LOCAL
int main()
{
    int n, c, q;
    cin >> n >> c >> q;
    vector<int> t(c), x(c), y(c), w(q), p(q);
    for (int i = 0; i < c; i++)
    {
        cin >> t[i] >> x[i] >> y[i];
    }
    for (int i = 0; i < q; i++)
    {
        cin >> w[i] >> p[i];
    }
    vector<int> ans = simulateCollapse(n, t, x, y, w, p);
    for (int i = 0; i < q; i++)
    {
        cout << ans[i] << "\n";
    }
}
#endif // LOCAL

Compilation message

collapse.cpp: In function 'void solve(int, int, int, int)':
collapse.cpp:91:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (cuts.size() != ss) Cut();
                    ~~~~~~~~~~~~^~~~~
collapse.cpp:102:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (cuts.size() != ss) Cut();
            ~~~~~~~~~~~~^~~~~
collapse.cpp:108:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (cuts.size() != ss) Cut();
            ~~~~~~~~~~~~^~~~~
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:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size(); i++)
                     ~~^~~~~~~~~~
collapse.cpp:141: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:165:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < w.size(); i++)
                     ~~^~~~~~~~~~
collapse.cpp:174:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < times.size(); i++)
                     ~~^~~~~~~~~~~~~~
collapse.cpp:179: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 12 ms 14848 KB Output is correct
3 Correct 12 ms 14848 KB Output is correct
4 Correct 12 ms 14848 KB Output is correct
5 Correct 24 ms 15232 KB Output is correct
6 Correct 112 ms 15736 KB Output is correct
7 Correct 32 ms 14976 KB Output is correct
8 Correct 34 ms 14976 KB Output is correct
9 Correct 142 ms 15480 KB Output is correct
10 Correct 158 ms 15480 KB Output is correct
11 Correct 383 ms 15864 KB Output is correct
12 Correct 314 ms 15992 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 20972 KB Output is correct
2 Correct 61 ms 21100 KB Output is correct
3 Correct 292 ms 28652 KB Output is correct
4 Correct 68 ms 21100 KB Output is correct
5 Correct 1053 ms 28772 KB Output is correct
6 Correct 1444 ms 21904 KB Output is correct
7 Correct 4619 ms 39856 KB Output is correct
8 Correct 1639 ms 29160 KB Output is correct
9 Correct 8082 ms 22624 KB Output is correct
10 Correct 8125 ms 22860 KB Output is correct
11 Correct 10232 ms 22928 KB Output is correct
12 Correct 5042 ms 31316 KB Output is correct
13 Correct 8611 ms 34548 KB Output is correct
14 Execution timed out 15096 ms 38960 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 20852 KB Output is correct
2 Correct 63 ms 20844 KB Output is correct
3 Correct 80 ms 20844 KB Output is correct
4 Correct 73 ms 20824 KB Output is correct
5 Correct 298 ms 20848 KB Output is correct
6 Correct 2040 ms 21536 KB Output is correct
7 Correct 4218 ms 32480 KB Output is correct
8 Correct 6489 ms 37704 KB Output is correct
9 Correct 8695 ms 22624 KB Output is correct
10 Correct 11658 ms 22720 KB Output is correct
11 Correct 10952 ms 39896 KB Output is correct
12 Correct 14304 ms 39996 KB Output is correct
13 Correct 11022 ms 42344 KB Output is correct
14 Correct 14241 ms 42928 KB Output is correct
15 Correct 11677 ms 42292 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15232 KB Output is correct
2 Correct 12 ms 14848 KB Output is correct
3 Correct 12 ms 14848 KB Output is correct
4 Correct 12 ms 14848 KB Output is correct
5 Correct 24 ms 15232 KB Output is correct
6 Correct 112 ms 15736 KB Output is correct
7 Correct 32 ms 14976 KB Output is correct
8 Correct 34 ms 14976 KB Output is correct
9 Correct 142 ms 15480 KB Output is correct
10 Correct 158 ms 15480 KB Output is correct
11 Correct 383 ms 15864 KB Output is correct
12 Correct 314 ms 15992 KB Output is correct
13 Correct 45 ms 20972 KB Output is correct
14 Correct 61 ms 21100 KB Output is correct
15 Correct 292 ms 28652 KB Output is correct
16 Correct 68 ms 21100 KB Output is correct
17 Correct 1053 ms 28772 KB Output is correct
18 Correct 1444 ms 21904 KB Output is correct
19 Correct 4619 ms 39856 KB Output is correct
20 Correct 1639 ms 29160 KB Output is correct
21 Correct 8082 ms 22624 KB Output is correct
22 Correct 8125 ms 22860 KB Output is correct
23 Correct 10232 ms 22928 KB Output is correct
24 Correct 5042 ms 31316 KB Output is correct
25 Correct 8611 ms 34548 KB Output is correct
26 Execution timed out 15096 ms 38960 KB Time limit exceeded
27 Halted 0 ms 0 KB -