oj.uz

답안 #255912

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

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<pair<int, int> > times(q);
    for (int i = 0; i < q; i++)
    {
        times[i] = {w[i], i};
    }
    sort(times.begin(), times.end());
    vector<int> pt(p.size());
    for (int i = 0; i < q; i++)
    {
        pt[i] = p[times[i].second];
    }
    DCP(x, y, times, pt, 0, n);
    for (int i = 0; i < q; i++)
    {
        answer[times[i].second] = times[i].first;
    }
    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)
                ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15104 KB Output is correct
2 Correct 13 ms 14848 KB Output is correct
3 Correct 11 ms 14848 KB Output is correct
4 Correct 13 ms 14848 KB Output is correct
5 Correct 26 ms 15104 KB Output is correct
6 Correct 113 ms 15584 KB Output is correct
7 Correct 31 ms 14976 KB Output is correct
8 Correct 34 ms 14968 KB Output is correct
9 Correct 125 ms 15232 KB Output is correct
10 Correct 157 ms 15476 KB Output is correct
11 Correct 392 ms 15608 KB Output is correct
12 Correct 312 ms 15616 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 19968 KB Output is correct
2 Correct 53 ms 19960 KB Output is correct
3 Correct 2390 ms 25176 KB Output is correct
4 Correct 65 ms 20088 KB Output is correct
5 Correct 3234 ms 25132 KB Output is correct
6 Correct 1436 ms 20732 KB Output is correct
7 Execution timed out 15060 ms 34296 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 19960 KB Output is correct
2 Correct 66 ms 20084 KB Output is correct
3 Correct 63 ms 20472 KB Output is correct
4 Correct 68 ms 20560 KB Output is correct
5 Correct 293 ms 20728 KB Output is correct
6 Correct 1892 ms 21540 KB Output is correct
7 Execution timed out 15055 ms 32380 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 15104 KB Output is correct
2 Correct 13 ms 14848 KB Output is correct
3 Correct 11 ms 14848 KB Output is correct
4 Correct 13 ms 14848 KB Output is correct
5 Correct 26 ms 15104 KB Output is correct
6 Correct 113 ms 15584 KB Output is correct
7 Correct 31 ms 14976 KB Output is correct
8 Correct 34 ms 14968 KB Output is correct
9 Correct 125 ms 15232 KB Output is correct
10 Correct 157 ms 15476 KB Output is correct
11 Correct 392 ms 15608 KB Output is correct
12 Correct 312 ms 15616 KB Output is correct
13 Correct 41 ms 19968 KB Output is correct
14 Correct 53 ms 19960 KB Output is correct
15 Correct 2390 ms 25176 KB Output is correct
16 Correct 65 ms 20088 KB Output is correct
17 Correct 3234 ms 25132 KB Output is correct
18 Correct 1436 ms 20732 KB Output is correct
19 Execution timed out 15060 ms 34296 KB Time limit exceeded
20 Halted 0 ms 0 KB -