oj.uz

답안 #255929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255929 2020-08-02T05:56:38 Z IgorI Collapse (JOI18_collapse) C++17
5 / 100
 1120 ms 59368 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 = 2000;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 15232 KB Output is correct
2 Correct 11 ms 14848 KB Output is correct
3 Correct 13 ms 14848 KB Output is correct
4 Correct 12 ms 14848 KB Output is correct
5 Correct 23 ms 15232 KB Output is correct
6 Correct 59 ms 15668 KB Output is correct
7 Correct 32 ms 14976 KB Output is correct
8 Correct 49 ms 14976 KB Output is correct
9 Correct 71 ms 15360 KB Output is correct
10 Correct 92 ms 15480 KB Output is correct
11 Correct 132 ms 15864 KB Output is correct
12 Correct 119 ms 15908 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 21100 KB Output is correct
2 Correct 70 ms 21100 KB Output is correct
3 Correct 296 ms 28860 KB Output is correct
4 Correct 71 ms 21100 KB Output is correct
5 Correct 1120 ms 29160 KB Output is correct
6 Correct 451 ms 22684 KB Output is correct
7 Runtime error 238 ms 59368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 20972 KB Output is correct
2 Correct 65 ms 20972 KB Output is correct
3 Correct 65 ms 21100 KB Output is correct
4 Correct 86 ms 21100 KB Output is correct
5 Correct 320 ms 21256 KB Output is correct
6 Correct 702 ms 20160 KB Output is correct
7 Runtime error 194 ms 52264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 15232 KB Output is correct
2 Correct 11 ms 14848 KB Output is correct
3 Correct 13 ms 14848 KB Output is correct
4 Correct 12 ms 14848 KB Output is correct
5 Correct 23 ms 15232 KB Output is correct
6 Correct 59 ms 15668 KB Output is correct
7 Correct 32 ms 14976 KB Output is correct
8 Correct 49 ms 14976 KB Output is correct
9 Correct 71 ms 15360 KB Output is correct
10 Correct 92 ms 15480 KB Output is correct
11 Correct 132 ms 15864 KB Output is correct
12 Correct 119 ms 15908 KB Output is correct
13 Correct 49 ms 21100 KB Output is correct
14 Correct 70 ms 21100 KB Output is correct
15 Correct 296 ms 28860 KB Output is correct
16 Correct 71 ms 21100 KB Output is correct
17 Correct 1120 ms 29160 KB Output is correct
18 Correct 451 ms 22684 KB Output is correct
19 Runtime error 238 ms 59368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -