Submission #939669

#	Time	Username	Problem	Language	Result	Execution time	Memory
939669		HiepVu217	Bridges (APIO19_bridges)	C++17	0 / 100	1112 ms	7660 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 17, M = 1e3;
int n, m, q;
int u[N], v[N], w[N], t[N], x[N], y[N];
int par[N], sz[N], ans[N];
bool change[N];
vector <int> ed[N];
stack <int> rb;
int root (int u)
{
    while (u != par[u])
    {
        u = par[u];
    }
    return u;
}
void join (int u, int v)
{
    int ru = root(u), rv = root(v);
    if (ru == rv)
    {
        return;
    }
    if (sz[ru] < sz[rv])
    {
        swap (ru, rv);
    }
    rb.push(rv);
    par[rv] = ru;
    sz[ru] += sz[rv];
}
void rollback (int x)
{
	while (rb.size() > x)
    {
		int s = rb.top();
		rb.pop();
		sz[par[s]] -= sz[s];
		par[s] = s;
	}
}
bool cmp1 (int a, int b)
{
    return w[a] > w[b];
}
bool cmp2 (int a, int b)
{
    return y[a] > y[b];
}
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] >> w[i];
    }
    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        cin >> t[i] >> x[i] >> y[i];
    }
    for (int l = 1, r = min (q, l + M - 1); l <= q; l += M)
    {
        iota (par + 1, par + n + 1, 1);
        fill (sz + 1, sz + n + 1, 1);
        fill (change + 1, change + m + 1, 0);
        vector <int> ask, newed, olded;
        for (int i = l; i <= r; ++i)
        {
            if (t[i] == 1)
            {
                change[x[i]] = 1;
                newed.push_back(i);
            }
            else
            {
                ask.push_back(i);
            }
        }
        for (int i = 1; i <= m; ++i)
        {
            if (!change[i])
            {
                olded.push_back(i);
            }
        }
        for (int i = l; i <= r; ++i)
        {
            if (t[i] == 1)
            {
                w[x[i]] = y[i];
            }
            else
            {
                ed[i].clear();
                for (int j: newed)
                {
                    if (y[i] <= w[x[j]])
                    {
                        ed[i].push_back(x[j]);
                    }
                }
            }
        }
        sort (olded.begin(), olded.end(), cmp1);
        sort (ask.begin(), ask.end(), cmp2);
        int j = 0;
        for (int i: ask)
        {
            while (j < olded.size() && w[olded[j]] >= y[i])
            {
                join (u[olded[j]], v[olded[j]]);
                ++j;
            }
            int s = rb.size();
            for (int j: ed[i])
            {
                join (u[j], v[j]);
            }
            ans[i] = sz[root(x[i])];
            rollback(s);
        }
    }
    for (int i = 1; i <= q; ++i)
    {
        if (t[i] == 2)
        {
            cout << ans[i] << "\n";
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:35:19: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |  while (rb.size() > x)
      |         ~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             while (j < olded.size() && w[olded[j]] >= y[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