Submission #623436

#	Time	Username	Problem	Language	Result	Execution time	Memory
623436		messiuuuuu	Bridges (APIO19_bridges)	C++17	100 / 100	2327 ms	141552 KiB

bridges

///
#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e5 + 5;
const ll INF = 1e18 + 5;
const int BS = 600;

int n, m;
pair<int, int> edge[MAXN];
int w[MAXN];

void Input()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v >> w[i];
        edge[i] = {u, v};
    }
}

pair<int, int> qu[MAXN];
vector<int> thaydoi[MAXN];
bool isc[MAXN];
int ans[MAXN];
int lab[MAXN];

struct TRb
{
    int u, v, labu, labv;
};

vector<TRb> rb;

void rollback(int sz)
{
    while (rb.size() > sz)
    {
        auto last = rb.back();
        rb.pop_back();
        lab[last.u] = last.labu;
        lab[last.v] = last.labv;
    }
}

int FindSet(int u)
{
    return lab[u] < 0 ? u : FindSet(lab[u]);
}

void Unite(int u, int v)
{
    u = FindSet(u);
    v = FindSet(v);
    if (u == v)
        return;
    if (lab[u] > lab[v])
        swap(u, v);
    rb.pb({u, v, lab[u], lab[v]});
    lab[u] += lab[v];
    lab[v] = u;
}

void Solve()
{
    int q;
    cin >> q;
    vector<int> cse(m);
    iota(cse.begin(), cse.end(), 1);
    for (int bl = 1; bl <= (q + BS - 1) / BS; bl++)
    {
        fill(lab, lab + 1 + n, -1);
        sort(cse.begin(), cse.end(), [](int i, int j)
        {
            return w[i] > w[j];
        });
        vector<int> t1, t2;
        int lf = (bl - 1) * BS + 1, rf = min(q, bl * BS);
        for (int i = lf; i <= rf; i++)
        {
            int t;
            cin >> t >> qu[i].fi >> qu[i].se;
            if (t == 1)
            {
                if (thaydoi[qu[i].fi].empty())
                {
                    t1.pb(qu[i].fi);
                }
                thaydoi[qu[i].fi].pb(i);
            }
            else
            {
                t2.pb(i);
            }
        }
        sort(t2.begin(), t2.end(), [](int i, int j)
             {
                 return qu[i].se > qu[j].se;
             });
        int i = 0;
        for (int id : t2)
        {
            while (i < m && w[cse[i]] >= qu[id].se)
            {
                if (!thaydoi[cse[i]].empty())
                {
                    i++;
                    continue;
                }
                Unite(edge[cse[i]].fi, edge[cse[i]].se);
                i++;
            }

            int sz = rb.size();
            for (int j : t1)
            {
                int p = lower_bound(thaydoi[j].begin(), thaydoi[j].end(), id) - thaydoi[j].begin() - 1;
                int w1 = p < 0 ? w[j] : qu[thaydoi[j][p]].se;
                if (w1 >= qu[id].se)
                    Unite(edge[j].fi, edge[j].se);
            }

            ans[id] = -lab[FindSet(qu[id].fi)];
            //assert(1 < 0);
            rollback(sz);
        }
        for (int id : t1)
        {
            w[id] = qu[thaydoi[id].back()].se;
            thaydoi[id].clear();
        }
    }
    for (int i = 1; i <= q; i++)
    {
        if (ans[i])
            cout << ans[i] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(task".INP","r"))
    {
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    Input();
    Solve();
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:44:22: warning: comparison of integer expressions of different signedness: 'std::vector<TRb>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     while (rb.size() > sz)
      |            ~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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