Submission #157453

#	Time	Username	Problem	Language	Result	Execution time	Memory
157453		combi1k1	Bridges (APIO19_bridges)	C++14	46 / 100	3041 ms	11776 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e5 + 5;
const int   B   = 300;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define sz(x)   x.size()
#define X       first
#define Y       second

typedef pair<int,int>   ii;
typedef pair<int,ii>    pii;
typedef vector<pii>     vi;

struct Edge {
    int x, y;
    int w, i;
    bool operator < (const Edge &a) const   {
        return  ii(w,i) > ii(a.w,a.i);
    }
};
struct Ques {
    int mas, ver, idx;
    bool operator < (const Ques& a) const   {
        return  mas > a.mas;
    }
};

bool uV[N], uE[N];

namespace DSU   {
    int p[N], s[N];
    int lead(int x) {
        return  p[x] == x ? x : p[x] = lead(p[x]);
    }
    int join(int x,int y)   {
        x = lead(x);
        y = lead(y);
        if (x == y) return  0;
        if (uV[y])  swap(x,y);
        if (uV[x] == uV[y] && s[x] < s[y])
            swap(x,y);
        p[y] = x;
        s[x] += s[y];
        return  1;
    }
};

set<Edge>   E;
int n, m;
int x[N], y[N], w[N];

void calc(vector<Ques>  qr) {
    iota(DSU::p + 1,DSU::p + 1 + n,1);
    fill(DSU::s + 1,DSU::s + 1 + n,1);
    fill(uV + 1,uV + 1 + n,0);
    fill(uE + 1,uE + 1 + m,0);
    vector<Ques>    sta;
    vector<int>     vx;
    vector<int>     ed;
    map<int,vi> mp;
    for(Ques t : qr)    {
        if(!t.idx)  uE[t.ver] = 1,  uV[x[t.ver]] = uV[y[t.ver]] = 1;
        else        sta.pb(t),      uV[t.ver] = 1;
    }
    for(int i = 1 ; i <= n ; ++i)   if (uV[i])  vx.pb(i);
    for(int i = 1 ; i <= m ; ++i)   if (uE[i])  ed.pb(i);
    sort(all(sta));
    auto it = E.begin();
    for(Ques t : sta)   {
        while (it != E.end() && (*it).w >= t.mas)   {
            if(!uE[(*it).i])    DSU::join((*it).x,(*it).y);
            it++;
        }
        for(int x : vx) mp[t.idx].pb(pii(x,{DSU::lead(x),DSU::s[DSU::p[x]]}));
    }
    for(Ques q : qr)    {
        if(!q.idx)  {
            Edge it = *E.find({x[q.ver],y[q.ver],w[q.ver],q.ver});
            E.erase(it);    it.w = w[q.ver] = q.mas;
            E.insert(it);   continue;
        }
        for(pii t : mp[q.idx])  DSU::p[t.X] = t.Y.X, DSU::s[t.X] = t.Y.Y;
        for(int i : ed) if (w[i] >= q.mas)
            DSU::join(x[i],y[i]);
        cout << DSU::s[DSU::lead(q.ver)] << "\n";
    }
}

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 >> x[i] >> y[i] >> w[i];
        E.insert({x[i],y[i],w[i],i});
    }

    int q;  cin >> q;

    vector<Ques>    v;

    for(int i = 1 ; i <= q ; ++i)   {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) v.pb({y,x,0});
        if (t == 2) v.pb({y,x,i});
    }

    for(int i = 0 ; i < q ; i += B)
        calc(vector<Ques>(v.begin() + i,v.begin() + min(q,i + B)));
}

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