Submission #255902

#	Time	Username	Problem	Language	Result	Execution time	Memory
255902		IgorI	Collapse (JOI18_collapse)	C++17	0 / 100	15036 ms	17384 KiB

collapse

#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] = 0;
    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];

void solve(int le, int ri)
{
    if (le + 1 == ri)
    {
        if (v[le] == -1)
        {
            ans[le] = comp;
        }
        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);
    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);
    while (cuts.size() != ss) Cut();
}

void DCP(vector<int> x, vector<int> y, vector<pair<int, int> > &t, int z)
{
    Reset();
    map<pair<int, int>, int> open;
    int T = 0;
    int j = 0;
    for (int i = 0; i < x.size(); i++)
    {
        if (y[i] <= z || z + 1 <= 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;
            T++;
            j++;
        }
    }
    #ifdef LOCAL
    cout << "<> T = " << T << endl;
    for (int i = 0; i < T; i++)
    {
        cout << v[i] << " " << u[i] << " " << L[i] << " " << R[i] << endl;
    }
    #endif // LOCAL
    solve(0, T);
    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++;
    }
    vector<int> answer(q);
    int z = p[0];
    vector<pair<int, int> > times(q);
    for (int i = 0; i < q; i++)
    {
        times[i] = {w[i], i};
    }
    sort(times.begin(), times.end());
    DCP(x, y, times, z);
    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 (stderr)

collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (cuts.size() != ss) Cut();
            ~~~~~~~~~~~~^~~~~
collapse.cpp:83: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> >&, int)':
collapse.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size(); i++)
                     ~~^~~~~~~~~~
collapse.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < t.size() && i == t[j].first)
                ~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35