Submission #1266329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266329		son2008	Bridges (APIO19_bridges)	C++20	100 / 100	1737 ms	6944 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define fi first
#define se second
// #define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int, ii>
#define iiii pair<ii, ii>
#define base 29
#define eps 1e-8
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
int dx[] = {0LL, 0LL, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0LL, 0LL, 1, -1, 1, -1};
const int maxn = 5e4 + 5, S = 1500, inf = 1e9;
const int mod = 1e9 + 7;
class DSU
{
private:
    vector<int> p, sz;
    // stores all history info related to merges
    vector<pair<int &, int>> history;

public:
    DSU(int n) : p(n), sz(n, 1)
    {
        iota(p.begin(), p.end(), 0);
        history.clear();
    }
    void reset(int n)
    {
        history.clear();
        for (int i = 1; i <= n; i++)
        {
            p[i] = i;
            sz[i] = 1;
        }
    }
    int acs(int x) { return (p[x] == x) ? x : acs(p[x]); }
    void join(int a, int b)
    {
        a = acs(a);
        b = acs(b);
        if (a == b)
        {
            return;
        }
        if (sz[a] < sz[b])
        {
            swap(a, b);
        }

        // add to history
        history.push_back({p[b], p[b]});
        history.push_back({sz[a], sz[a]});

        p[b] = a;
        sz[a] += sz[b];
    }
    int sl(int x)
    {
        return sz[acs(x)];
    }
    int snapshot() { return history.size(); }

    void rollback(int until)
    {
        while (snapshot() > until)
        {
            history.back().first = history.back().second;
            history.pop_back();
        }
    }
};
DSU dsu(maxn);
int n, m, q, cuoi[maxn << 1], ans[maxn << 1];
bool check_e[maxn << 1];
struct node
{
    int u, v, w;
} e[maxn << 1];
struct qr
{
    int t, x, y;
} tv[maxn << 1];
bool cmp2(int x, int y)
{
    return tv[x].y > tv[y].y;
}
bool cmp1(int x, int y)
{
    return e[x].w > e[y].w;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#define task "task"
    if (fopen(task ".inp", "r"))
    {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> tv[i].t >> tv[i].x >> tv[i].y;
    }
    for (int st = 1; st <= q; st += S)
    {
        int en = min(q, st + S - 1);
        vector<int> loai2;
        for (int i = st; i <= en; i++)
        {
            if (tv[i].t == 1)
            {
                check_e[tv[i].x] = true;
            }
            else
            {
                loai2.push_back(i);
            }
        }
        vector<int> edge;
        vector<int> loai1;
        for (int i = 1; i <= m; i++)
        {
            cuoi[i] = -1;
            if (!check_e[i])
            {
                edge.push_back(i);
            }
            else
            {
                loai1.push_back(i);
            }
        }
        dsu.rollback(0);
        sort(loai2.begin(), loai2.end(), cmp2);
        sort(edge.begin(), edge.end(), cmp1);
        int j = 0;
        for (int x : loai2)
        {
            while (j < edge.size() && tv[x].y <= e[edge[j]].w)
            {
                dsu.join(e[edge[j]].u, e[edge[j]].v);
                j++;
            }
            int siz = dsu.snapshot();
            for (int i = st; i <= x; i++)
            {
                if (tv[i].t == 1)
                {
                    cuoi[tv[i].x] = tv[i].y;
                }
            }
            for (int id : loai1)
            {
                if (cuoi[id] != -1)
                {
                    if (cuoi[id] >= tv[x].y)
                    {
                        dsu.join(e[id].u, e[id].v);
                    }
                }
                else if (e[id].w >= tv[x].y)
                {
                    dsu.join(e[id].u, e[id].v);
                }
            }
            for (int i = st; i <= x; i++)
            {
                if (tv[i].t == 1)
                {
                    cuoi[tv[i].x] = -1;
                }
            }
            ans[x] = dsu.sl(tv[x].x);
            dsu.rollback(siz);
        }
        for (int i = st; i <= en; i++)
        {
            if (tv[i].t == 1)
            {
                check_e[tv[i].x] = false;
                e[tv[i].x].w = tv[i].y;
            }
        }
    }
    for (int i = 1; i <= q; i++)
    {
        if (tv[i].t == 2)
            cout << ans[i] << '\n';
    }
    cerr << endl
         << "TIME : " << clock() * 0.001 << "s" << endl;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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