oj.uz

답안 #255930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255930 2020-08-02T05:57:09 Z IgorI Collapse (JOI18_collapse) C++17
5 / 100
 1068 ms 58984 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 = 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;
    }
    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 13 ms 15104 KB Output is correct
2 Correct 11 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 15104 KB Output is correct
6 Correct 66 ms 15616 KB Output is correct
7 Correct 33 ms 14976 KB Output is correct
8 Correct 32 ms 14976 KB Output is correct
9 Correct 126 ms 15232 KB Output is correct
10 Correct 93 ms 15360 KB Output is correct
11 Correct 179 ms 15736 KB Output is correct
12 Correct 130 ms 15744 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 20844 KB Output is correct
2 Correct 63 ms 20844 KB Output is correct
3 Correct 326 ms 28476 KB Output is correct
4 Correct 76 ms 20844 KB Output is correct
5 Correct 1068 ms 28640 KB Output is correct
6 Correct 1002 ms 22416 KB Output is correct
7 Runtime error 225 ms 58984 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 47 ms 20844 KB Output is correct
2 Correct 58 ms 20844 KB Output is correct
3 Correct 65 ms 20844 KB Output is correct
4 Correct 71 ms 20844 KB Output is correct
5 Correct 291 ms 20976 KB Output is correct
6 Correct 899 ms 20152 KB Output is correct
7 Runtime error 178 ms 52008 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 13 ms 15104 KB Output is correct
2 Correct 11 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 15104 KB Output is correct
6 Correct 66 ms 15616 KB Output is correct
7 Correct 33 ms 14976 KB Output is correct
8 Correct 32 ms 14976 KB Output is correct
9 Correct 126 ms 15232 KB Output is correct
10 Correct 93 ms 15360 KB Output is correct
11 Correct 179 ms 15736 KB Output is correct
12 Correct 130 ms 15744 KB Output is correct
13 Correct 45 ms 20844 KB Output is correct
14 Correct 63 ms 20844 KB Output is correct
15 Correct 326 ms 28476 KB Output is correct
16 Correct 76 ms 20844 KB Output is correct
17 Correct 1068 ms 28640 KB Output is correct
18 Correct 1002 ms 22416 KB Output is correct
19 Runtime error 225 ms 58984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -