Submission #939616

#	Time	Username	Problem	Language	Result	Execution time	Memory
939616		HiepVu217	Bridges (APIO19_bridges)	C++17	0 / 100	985 ms	20676 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 17, M = 316;
int n, m, q;
int u[N], v[N], d[N], t[N], b[N], w[N];
int ti, num;
int par[N], sz[N], ans[N];
bool change[N];
vector <int> ask, newed, olded, ed[N];
struct version
{
    int ti, par, sz, u;
} rb[N];
int root (int u)
{
    if (u == par[u])
    {
        return u;
    }
    rb[++num] = {ti, par[u], sz[u], u};
    return par[u] = root(par[u]);
}
void join (int u, int v)
{
    int ru = root(u), rv = root(v);
    if (ru == rv)
    {
        return;
    }
    rb[++num] = {ti, par[ru], sz[ru], ru};
    rb[++num] = {ti, par[rv], sz[rv], rv};
    if (sz[ru] < sz[rv])
    {
        swap (ru, rv);
    }
    par[rv] = ru;
    sz[ru] += sz[rv];
}
void rollback (int ti)
{
    while (rb[num].ti == ti)
    {
        auto [t, p, s, u] = rb[num];
        par[u] = p;
        sz[u] = s;
        --num;
    }
}
bool cmp1 (int x, int y)
{
    return d[x] > d[y];
}
bool cmp2 (int x, int y)
{
    return w[x] > w[y];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> u[i] >> v[i] >> d[i];
    }
    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        cin >> t[i] >> b[i] >> w[i];
    }
    for (int l = 1, r = min (q, l + M - 1); l <= q; l += M)
    {
        for (int i = 1; i <= n; ++i)
        {
            par[i] = i, sz[i] = 1;
            change[i] = 0;
        }
        olded.clear();
        newed.clear();
        ask.clear();
        for (int i = l; i <= r; ++i)
        {
            if (t[i] == 1)
            {
                change[b[i]] = 1;
                newed.push_back(i);
            }
            else
            {
                ask.push_back(i);
            }
        }
        for (int i = l; i <= r; ++i)
        {
            if (t[i] == 1)
            {
                d[b[i]] = w[i];
            }
            else
            {
                ed[i].clear();
                for (int j: newed)
                {
                    if (w[i] <= d[b[j]])
                    {
                        ed[i].push_back(b[j]);
                    }
                }
            }
        }
        for (int i = 1; i <= m; ++i)
        {
            if (!change[i])
            {
                olded.push_back(i);
            }
        }
        sort (olded.begin(), olded.end(), cmp1);
        sort (ask.begin(), ask.end(), cmp2);
        int j = 0;
        for (int i: ask)
        {
            while (j < olded.size() && d[olded[j]] >= w[i])
            {
                join (u[olded[j]], v[olded[j]]);
                ++j;
            }
            ++ti;
            for (int x: ed[i])
            {
                join (u[x], v[x]);
            }
            ans[i] = sz[root(b[i])];
            rollback(ti);
        }
    }
    for (int i = 1; i <= q; ++i)
    {
        if (ans[i])
        {
            cout << ans[i] << "\n";
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             while (j < olded.size() && d[olded[j]] >= w[i])
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27