Submission #586747

#	Time	Username	Problem	Language	Result	Execution time	Memory
586747		danikoynov	Bridges (APIO19_bridges)	C++14	100 / 100	2325 ms	20448 KiB

bridges

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10, block = 1010;

struct edge
{
    int v, u, d;

    edge(int _v = 0, int _u = 0, int _d = 0)
    {
        v = _v;
        u = _u;
        d = _d;
    }
}e[maxn];

struct query
{
    int t, x, y;

    query(int _t = 0, int _x = 0, int _y = 0)
    {
        t = _t;
        x = _x;
        y = _y;
    }
}ask[maxn];



bool cmp_car(int id1,  int id2)
{
    return ask[id1].y > ask[id2].y;
}

bool cmp_edge(int id1, int id2)
{
    return e[id1].d > e[id2].d;
}
int n, m, q, ans[maxn];
bool changed[maxn];
vector < edge > to_join[block + 10];


struct DisjointSetUnion
{
    vector < int > par, sz;
    stack < pair < int, int > > st;

    DisjointSetUnion()
    {
        par.resize(n + 1);
        sz.resize(n + 1);

        for (int i = 1; i <= n; i ++)
        {
            par[i] = i;
            sz[i] = 1;
        }
    };

    void reset()
    {
        while(!st.empty())
            st.pop();

        for (int i = 1; i <= n; i ++)
        {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find_leader(int v)
    {
        while(par[v] != v)
            v = par[v];
        return v;
    }

    void unite(int v, int u)
    {
        ///cout << v << " --------- " << u << endl;
        v = find_leader(v);
        u = find_leader(u);
        if (v == u)
            return;
        if (sz[v] < sz[u])
            swap(v, u);
        sz[v] += sz[u];
        par[u] = v;
        st.push({v, u});
    }

    void rollback()
    {
        pair < int, int > cur = st.top();
        st.pop();
        sz[cur.first] -= sz[cur.second];
        par[cur.second] = cur.second;
    }
};
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
        cin >> e[i].v >> e[i].u >> e[i].d;

    cin >> q;
    for (int i = 1; i <= q; i ++)
        cin >> ask[i].t >> ask[i].x >> ask[i].y;

    DisjointSetUnion dsu;
    for (int l = 1; l <= q; l += block)
    {
        int r = min(q, l + block - 1);

        for (int i = 1; i <= m; i ++)
            changed[i] = false;

            for (int i = 0; i < block; i ++)
                to_join[i].clear();

        vector < int > upd, ask_car, unchanged;
        for (int i = l; i <= r; i ++)
        {
            if (ask[i].t == 1)
            {
                changed[ask[i].x] = 1;
                upd.push_back(i);
            }
            else
            {
                ask_car.push_back(i);
            }
        }

        for (int i = 1; i <= m; i ++)
            if (changed[i] == 0)
            unchanged.push_back(i);

        for (int i = l; i <= r; i ++)
        {
            if (ask[i].t == 1)
            {
                e[ask[i].x].d = ask[i].y;
            }
            else
            {
                for (int id : upd)
                {

                    if (e[ask[id].x].d >= ask[i].y)
                    {
                        to_join[i - l].push_back(e[ask[id].x]);
                    }
                }
            }
        }

        dsu.reset();
        sort(ask_car.begin(), ask_car.end(), cmp_car);
        sort(unchanged.begin(), unchanged.end(), cmp_edge);
        int ptr = 0;
        for (int i = 0; i < ask_car.size(); i ++)
        {
            ///cout << i << " : " << e[unchanged[ptr]].d << " " << ask[ask_car[i]].y << endl;
            while(ptr < unchanged.size() && e[unchanged[ptr]].d >= ask[ask_car[i]].y)
                dsu.unite(e[unchanged[ptr]].v, e[unchanged[ptr]].u), ptr ++;

            int cur_sz = dsu.st.size();
            /**for (int i = 1; i <= n; i ++)
                cout << dsu.par[i] << " ";
            cout << endl;*/
            for (edge cur : to_join[ask_car[i] - l])
            {
               /// cout << i << " yes" << endl;
                dsu.unite(cur.v, cur.u);
            }

            ans[ask_car[i]] = dsu.sz[dsu.find_leader(ask[ask_car[i]].x)];
            ///cout << i << " ::: " << ans[ask_car[i]] << endl;
            while(dsu.st.size() > cur_sz)
                dsu.rollback();
            /**for (int i = 1; i <= n; i ++)
            cout << dsu.par[i] << " ";
            cout << endl;
            cout << "-----------" << endl;*/

        }

    }

    for (int i = 1; i <= q; i ++)
        if (ask[i].t == 2)
        cout << ans[i] << endl;
}

int main()
{
    speed();
    solve();
    return 0;
}

/**
3 4
1 2 5
2 3 2
3 1 4
2 3 8
4
2 1 5
1 4 1
2 2 5
1 1 1
*/

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:137:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  137 |         for (int i = 1; i <= m; i ++)
      |         ^~~
bridges.cpp:140:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  140 |             for (int i = 0; i < block; i ++)
      |             ^~~
bridges.cpp:184:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |         for (int i = 0; i < ask_car.size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~~
bridges.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |             while(ptr < unchanged.size() && e[unchanged[ptr]].d >= ask[ask_car[i]].y)
      |                   ~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:202:33: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  202 |             while(dsu.st.size() > cur_sz)
      |                   ~~~~~~~~~~~~~~^~~~~~~~

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