Submission #157447

#	Time	Username	Problem	Language	Result	Execution time	Memory
157447		combi1k1	Bridges (APIO19_bridges)	C++14	13 / 100	3036 ms	524292 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

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

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define X       first
#define Y       second
#define ver     tuple<int,int,int>

bitset<N>   uV;
bitset<N>   uE;

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

struct Edge {
    int x, y;
    int w;
}   E[N];
struct Ques {
    int i, w;
    int idx;
}   Q[N];

int n, m;
vector<int> edge;
vector<ver> stat[N];

void calc(vector<int> qr)   {
    iota(DSU::p,DSU::p + n,0);
    fill(DSU::s,DSU::s + n,1);
    uV = uE = 0;

    vector<int> vx;
    vector<int> ed;
    vector<int> ques;

    for(int i : qr) {
        if (Q[i].idx)   uV[Q[i].i] = 1, ques.pb(i);
        if(!Q[i].idx){  uE[Q[i].i] = 1;
            uV[E[Q[i].i].x] = 1;
            uV[E[Q[i].i].y] = 1;
        }
    }
    for(int i = 0 ; i < n ; ++i)    if (uV[i])  vx.pb(i);
    for(int i = 0 ; i < m ; ++i)    if (uE[i])  ed.pb(i);

    sort(all(ques),[&](const int &a,const int &b)   {
         return  Q[a].w > Q[b].w;
    });
    sort(all(edge),[&](const int &a,const int &b)   {
         return  E[a].w > E[b].w;
    });

    int ptr = 0;

    for(int i : ques)   {
        for(; ptr < m ; ++ptr)  {
            int j = edge[ptr];
            if (E[j].w < Q[i].w)    break;
            if(uE[j])   continue;
            DSU::join(E[j].x,E[j].y);
        }
        for(int x : vx)
            stat[Q[i].idx].pb(make_tuple(x,lead(x),Size(x)));
    }
    for(int i : qr) {
        if(!Q[i].idx)   E[Q[i].i].w = Q[i].w;
        if (Q[i].idx)   {
            for(ver V : stat[Q[i].idx]) {
                int x, P, S;
                tie(x, P, S) = V;
                DSU::p[x] = P;
                DSU::s[x] = S;
            }
            for(int j : ed)  if (E[j].w >= Q[i].w)
                DSU::join(E[j].x,E[j].y);
            stat[Q[i].idx].clear();
            cout <<  Size(Q[i].i) << "\n";
        }
    }
}

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

    cin >> n >> m;

    for(int i = 0 ; i < m ; ++i)    {
        cin >> E[i].x;  E[i].x--;
        cin >> E[i].y;  E[i].y--;
        cin >> E[i].w;  edge.pb(i);
    }

    int q;
    cin >> q;

    vector<int> v;

    for(int i = 1 ; i <= q ; ++i)   {
        int t;  cin >> t;
        cin >> Q[i].i;  Q[i].i--;
        cin >> Q[i].w;  v.pb(i);
        Q[i].idx = (t - 1) * i;
    }

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

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