Submission #713781

#	Time	Username	Problem	Language	Result	Execution time	Memory
713781		ooo	Bridges (APIO19_bridges)	C++14	16 / 100	3031 ms	3864 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

const int nu = 1e5+5;
typedef pair<int, int> cap1;
typedef pair< pair<int, int>, pair<int, int> > cap2;
#define fi first
#define se second
int n, m, query, hang[nu], root[nu];
int type[nu], u[nu], v[nu], a[nu], b[nu];
int c[nu], w[nu], ans[nu];
bool dd[nu];
stack<cap2> st;
vector<int> q;
vector<cap1> temp;
int findroot(int x)
{
    if(x == root[x]) return x;
    else return findroot(root[x]);
}
void dsu(int x, int y)
{
    hang[y] += hang[x];
    root[x] = y;
}
void rollback(int x, int y)
{
    root[x] = st.top().fi.fi; root[y] = st.top().fi.se;
    hang[x] = st.top().se.fi; hang[y] = st.top().se.se;

    st.pop();
}
bool ss(int x, int y)
{
    return (w[x] > w[y]);
}
bool ss2(int x, int y)
{
    return (b[x] > b[y]);
}
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 >> query;
    for(int i = 1; i <= query; ++i) cin >> type[i] >> a[i] >> b[i];

    int can = sqrt(query);
    int x = query/can;
    if(query%can > 0) x++;
    for(int i = 1; i <= x; ++i)
    {
        int l = (i-1)*x+1;
        int r = min(i*x, query);

        for(int j = l; j <= r; ++j)
        if(type[j] == 2) q.push_back(j);
        else dd[a[j]] = true;
        sort(q.begin(), q.end(), ss2);

        for(int j = 1; j <= m; ++j)
        if(dd[j] == false) c[j] = j; else c[j] = 0;

        for(int j = 1; j <= n; ++j) root[j] = j, hang[j] = 1;
        sort(c+1, c+1+m, ss);

        for(int j = l; j <= r; ++j)
        if(type[j] == 1) dd[a[j]] = false;

        int j = 0; int k = 1;
        while(j < int(q.size()))
        {
            while(k <= m && w[c[k]] >= b[q[j]])
            {
                int x = findroot(u[c[k]]);
                int y = findroot(v[c[k]]);
                if(hang[x] > hang[y]) swap(x, y);
                if(x != y) dsu(x, y);
                k++;
            }

            for(int h = q[j]; h >= l; --h)
            if(type[h] == 1 && b[h] >= b[q[j]] && !dd[a[h]])
            {
                int x = findroot(u[a[h]]);
                int y = findroot(v[a[h]]);
                if(x != y)
                {
                    if(hang[x] > hang[y]) swap(x, y);
                    st.push({{root[x], root[y]}, {hang[x], hang[y]}});
                    temp.push_back({x, y});
                    dsu(x, y);
                }
                dd[a[h]] = true;
            }
            for(int h = l; h <= q[j]; ++h) if(type[h] == 1) dd[a[h]] = false;

            for(int h = q[j]+1; h <= r; ++h)
            if(type[h] == 1 && w[a[h]] >= b[q[j]])
            {
                int x = findroot(u[a[h]]);
                int y = findroot(v[a[h]]);

                if(x != y)
                {
                    if(hang[x] > hang[y]) swap(x, y);
                    st.push({{root[x], root[y]}, {hang[x], hang[y]}});
                    temp.push_back({x, y});
                    dsu(x, y);
                }
            }

            ans[q[j]] = hang[findroot(a[q[j]])];

            while(!temp.empty()) rollback(temp.back().fi, temp.back().se), temp.pop_back();
            j++;
        }

        for(int j = l; j <= r; ++j) if(type[j] == 1) w[a[j]] = b[j];
        q.clear();
    }
    for(int i = 1; i <= query; ++i)
    if(ans[i] > 0) cout << ans[i] << '\n';
    return 0;
}

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