Submission #713919

#	Time	Username	Problem	Language	Result	Execution time	Memory
713919		ooo	Bridges (APIO19_bridges)	C++14	100 / 100	2379 ms	10828 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 w[nu], ans[nu];
int c[nu*2], d[nu*2], e[nu*2], pos[nu*2], trc[nu*2], pp[nu*2];
bool dd[nu], kt[nu], check[nu*2];
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 (e[x] > e[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;
    int len = 0;
    for(int i = 1; i <= m; ++i) cin >> u[i] >> v[i] >> w[i], c[++len] = i, d[len] = i, e[len] = w[i], pos[i] = i, check[i] = true;
    cin >> query;
    for(int i = 1; i <= query; ++i) cin >> type[i] >> a[i] >> b[i];
    int p = m;
    for(int i = 1; i <= query; ++i)
    if(type[i] == 1)
    {
        c[++len] = ++m, d[m] = a[i], e[m] = b[i];
        trc[m] = pos[a[i]];
        pos[a[i]] = m;
        pp[i] = m;
    }
    sort(c+1, c+1+len, ss);

    int can = sqrt(query);
    int x = query/can;
    if(query%can > 0) x++;
    for(int i = 1; i <= can; ++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 kt[a[j]] = true;

        sort(q.begin(), q.end(), ss2);


        for(int j = 1; j <= n; ++j) root[j] = j, hang[j] = 1;
        int j = 0; int k = 1;
        while(j < int(q.size()))
        {
            while(k <= len && e[c[k]] >= b[q[j]])
            {
                if(check[c[k]] && !kt[d[c[k]]])
                {
                    int x = findroot(u[d[c[k]]]);
                    int y = findroot(v[d[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(!dd[a[h]] && type[h] == 1)
            {
                if(b[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);
                    }
                }
                dd[a[h]] = true;
            }

            for(int h = q[j]+1; h <= r; ++h)
            if(type[h] == 1 && w[a[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);
                }
            }
            for(int h = l; h <= q[j]; ++h) if(type[h] == 1) dd[a[h]] = false;
            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)
        {
            check[trc[pp[j]]] = false;
            check[pp[j]] = true;
            kt[a[j]] = false;
            w[a[j]] = b[j];
        }
        q.clear();
    }
    for(int i = 1; i <= query; ++i)
    if(ans[i] > 0) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:51:9: warning: unused variable 'p' [-Wunused-variable]
   51 |     int p = m;
      |         ^

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