Submission #993342

#	Time	Username	Problem	Language	Result	Execution time	Memory
993342		Chris_Black	Bridges (APIO19_bridges)	C++17	0 / 100	3003 ms	12612 KiB

bridges

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define pii pair<int, int>
#define ff first
#define ss second
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define ll long long

using namespace std;
const int N = 50009, M = 1e5 + 9, BUCKET = 330;

int n, m, q, ans[M];
bool seen[M], mod[M];

struct edge
{
    int u, v, d, id;

    bool operator < (edge const& oth) const noexcept
    {
        return d < oth.d;
    }

    bool operator > (edge const& oth) const noexcept
    {
        return oth < *this;
    }
};
vector<edge> edges;

struct query
{
    int t, p, v, ans;
};
vector<query> qs;

int dsu[N], sz[N];
stack<pii> stk;
int find(int x){return dsu[x] ? find(dsu[x]) : x;}
void unite(int x, int y)
{
    x = find(x), y = find(y);

    if(x == y)return;

    if(sz[x] > sz[y])swap(x, y);

    dsu[x] = y;
    sz[y] += sz[x];

    stk.push({x, y});
}
void RollBack()
{
    if(stk.empty())return;

    int x = stk.top().ff, y = stk.top().ss;
    stk.pop();

    dsu[x] = 0;
    sz[y] -= sz[x];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    FOR(i, 1, n)sz[i] = 1;

    edges.resize(m);
    FOR(i, 0, m - 1)
    {
        cin >> edges[i].u >> edges[i].v >> edges[i].d;
        edges[i].id = i + 1;
    }

    cin >> q;
    qs.resize(q);
    FOR(i, 0, q - 1)
        cin >> qs[i].t >> qs[i].p >> qs[i].v;


    for(int k = 0; k < q; k += BUCKET)
    {
        set<int> st;
        priority_queue<pii> toans;
        for(int i = k; i < min(q, k + BUCKET); ++i)
            if(qs[i].t == 1)
            {
                mod[qs[i].p] = true;
                st.insert(qs[i].p);
            }
            else toans.push({qs[i].v, i});

        priority_queue<edge> ing;
        for(auto e : edges)
            if(!mod[e.id])
                ing.push(e);

        while(!toans.empty())
        {
            int dx = toans.top().ff, p = toans.top().ss;
            toans.pop();

            while(!ing.empty() && ing.top().d >= dx)
            {
                unite(ing.top().u, ing.top().v);
                ing.pop();
            }
            int s = stk.size();

            for(int i = p; i >= k; --i)
                if(qs[i].t == 1 && !seen[qs[i].p])
                {
                    seen[qs[i].p] = true;
                    if(qs[i].v >= dx)unite(edges[qs[i].p - 1].u, edges[qs[i].p - 1].v);
                }

            for(auto ind : st)
                if(!seen[ind] && edges[ind - 1].d >= dx)
                    unite(edges[ind - 1].u, edges[ind - 1].v);

            ans[p] = sz[find(qs[p].p)];

            for(int i = p; i >= k; --i)
                if(qs[i].t == 1)
                    seen[qs[i].p] = false;

            while(stk.size() != s)RollBack();
        }

        for(int i = k; i < min(q, k + BUCKET); ++i)
            if(qs[i].t == 1)mod[qs[i].p] = false;

        while(!stk.empty())stk.pop();
        FOR(i, 1, n)
        {
            dsu[i] = 0;
            sz[i] = 1;
        }
    }

    FOR(i, 0, q - 1)
        if(qs[i].t == 2)
            cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:135:30: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |             while(stk.size() != s)RollBack();
      |                   ~~~~~~~~~~~^~~~

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