Submission #216553

#	Time	Username	Problem	Language	Result	Execution time	Memory
216553		usachevd0	Bridges (APIO19_bridges)	C++14	100 / 100	1355 ms	10072 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define time(...) 42
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

mt19937 rng(time(0));
const int INF32 = 1e9 + 1337 + 228 + 1488;
const int BUBEN = 500;
const int maxV = 50004;
const int maxE = 100005;
const int maxQ = 100005;
int eV[maxE], eU[maxE], eF[maxE];
int qT[maxQ], qI[maxE], qF[maxE];

namespace dsu
{
    int q[maxV];
    vector< pair<int&, int> > stk;

    void init()
    {
        memset(q, 255, sizeof(q));
        stk.clear();
    }

    int gt(int a)
    {
        return q[a] < 0 ? a : gt(q[a]);
    }

    void un(int a, int b, bool memorize = false)
    {
        a = gt(a);
        b = gt(b);
        if (a == b) return;
        if (-q[a] > -q[b])
            swap(a, b);
        if (memorize)
        {
            stk.emplace_back(q[a], q[a]);
            stk.emplace_back(q[b], q[b]);
        }
        q[b] += q[a];
        q[a] = b;
    }

    void backtrack()
    {
        while (!stk.empty())
        {
            stk.back().fi = stk.back().se;
            stk.pop_back();
        }
    }
}

int ans[maxQ];

int e_ord[maxE];
int ge[maxE];
int be[maxE];
bool changes[maxE];

int mem_link[maxQ];
int mem[2 * BUBEN][2 * BUBEN];

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        cin >> eV[i] >> eU[i] >> eF[i];
    }
    iota(e_ord, e_ord + M, 1);
    sort(e_ord, e_ord + M, [&](int e1, int e2) -> bool
    {
        return eF[e1] > eF[e2];
    });

    int Q;
    cin >> Q;
    for (int t = 1; t <= Q; ++t)
    {
        cin >> qT[t] >> qI[t] >> qF[t];
    }
    for (int t1 = 1; t1 <= Q; t1 += BUBEN)
    {
//        cout << ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << endl;
        int t2 = min(Q, t1 + BUBEN - 1);
        for (int t = t1; t <= t2; ++t)
        {
            if (qT[t] == 1)
            {
                int e = qI[t];
                changes[e] = true;
            }
        }
        int ge_cnt = 0;
        int be_cnt = 0;
        for (int i = 0; i < M; ++i)
        {
            int e = e_ord[i];
            if (!changes[e])
            {
                ge[ge_cnt++] = e;
            }
            else
            {
                be[be_cnt++] = e;
            }
        }
        /*cout << "ge: "; for (int i = 0; i < ge_cnt; ++i) cout << ge[i] << ' '; cout << endl;
        cout << "    "; for (int i = 0; i < ge_cnt; ++i) cout << eF[ge[i]] << ' '; cout << endl;
        cout << "be: "; for (int i = 0; i < be_cnt; ++i) cout << be[i] << ' '; cout << endl;
        cout << "    "; for (int i = 0; i < be_cnt; ++i) cout << eF[be[i]] << ' '; cout << endl;/**/

        int mem_ptr = 0;
        vector<int> ask;
        for (int t = t1; t <= t2; ++t)
        {
            if (qT[t] == 1)
            {
                int e = qI[t];
                eF[e] = qF[t];
            }
            else
            {
                int v = qI[t];
                mem_link[t] = mem_ptr++;
                for (int i = 0; i < be_cnt; ++i)
                {
                    mem[mem_link[t]][i] = eF[be[i]];
                }
                ask.push_back(t);
            }
        }
        sort(all(ask), [&](int t1, int t2) -> bool
        {
            return qF[t1] > qF[t2];
        });
        dsu::init();
        int ge_ptr = 0;
        for (int ai = 0; ai < ask.size(); ++ai)
        {
            int t = ask[ai];
            while (ge_ptr < ge_cnt && eF[ge[ge_ptr]] >= qF[t])
            {
                int e = ge[ge_ptr++];
                dsu::un(eV[e], eU[e]);
            }
            
            for (int bi = 0; bi < be_cnt; ++bi)
            {
                int e = be[bi];
                int f = mem[mem_link[t]][bi];
                if (f >= qF[t])
                {
                    dsu::un(eV[e], eU[e], true);
                }
            }
            ans[t] = -dsu::q[dsu::gt(qI[t])];
            dsu::backtrack();
        }

        sort(be, be + be_cnt, [&](int e1, int e2) -> bool
        {
            return eF[e1] > eF[e2];
        });
        int ptr1 = 0, ptr2 = 0;
        for (int i = 0; i < M; ++i)
        {
            if (ptr2 < be_cnt && (ptr1 >= ge_cnt || eF[ge[ptr1]] < eF[be[ptr2]]))
            {
                e_ord[i] = be[ptr2++];
            }
            else 
            {
                e_ord[i] = ge[ptr1++];
            }
        }

        for (int t = t1; t <= t2; ++t)
        {
            if (qT[t] == 1)
            {
                changes[qI[t]] = false;
            }
        }
    }
    for (int t = 1; t <= Q; ++t)
        if (qT[t] == 2)
            cout << ans[t] << '\n';

    return 0;
}

Compilation message (stderr)

bridges.cpp:154:97: warning: "/*" within comment [-Wcomment]
         cout << "    "; for (int i = 0; i < be_cnt; ++i) cout << eF[be[i]] << ' '; cout << endl;/**/
                                                                                                  
bridges.cpp: In function 'int main()':
bridges.cpp:167:21: warning: unused variable 'v' [-Wunused-variable]
                 int v = qI[t];
                     ^
bridges.cpp:182:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int ai = 0; ai < ask.size(); ++ai)
                          ~~~^~~~~~~~~~~~

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