Submission #217951

#	Time	Username	Problem	Language	Result	Execution time	Memory
217951		gs18115	Bridges (APIO19_bridges)	C++14	100 / 100	1527 ms	8132 KiB

bridges

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
const int siz=500;
int pa[50010],sz[50010];
int par(int x)
{
    while(pa[x]!=0)
        x=pa[x];
    return x;
}
vector<pi>rbv;
inline void uni(int x,int y,bool rbf)
{
    x=par(x);
    y=par(y);
    if(x==y)
        return;
    if(sz[x]>sz[y])
        swap(x,y);
    if(rbf)
        rbv.eb(x,0),rbv.eb(y,sz[y]);
    pa[x]=y;
    sz[y]+=sz[x];
    return;
}
inline void init(int n)
{
    fill(pa+1,pa+n+1,0);
    fill(sz+1,sz+n+1,1);
    return;
}
inline void rb(pi&x)
{
    (x.se==0?pa[x.fi]:sz[x.fi])=x.se;
    return;
}
inline void rb()
{
    reverse(all(rbv));
    for(pi&t:rbv)
        rb(t);
    rbv.clear();
    return;
}
int eu[100010],ev[100010],ed[100010];
vector<int>edge;
bool chk[100010];
int n,m,q;
inline void solve(vector<pair<int,pi> >&v)
{
    fill(chk+1,chk+m+1,0);
    init(n);
    vector<int>change;
    for(auto&t:v)
        if(t.fi==1)
            chk[t.se.fi]=1,change.eb(t.se.fi);
    sort(all(change));
    change.erase(unique(all(change)),change.end());
    int C=0;
    multimap<int,pair<pi,vector<int> >,greater<int> >mp;
    for(auto&tq:v)
    {
        if(tq.fi==1)
            ed[tq.se.fi]=tq.se.se;
        else
        {
            vector<int>qv;
            for(int&te:change)
                if(ed[te]>=tq.se.se)
                    qv.eb(te);
            mp.ep(tq.se.se,make_pair(pi(tq.se.fi,C),qv));
            C++;
        }
    }
    v.clear();
    vector<int>ans(C);
    vector<int>cur;
    for(int&t:edge)
        if(!chk[t])
            cur.eb(t);
    int vi=0;
    for(auto&tq:mp)
    {
        while(vi<(int)cur.size()&&ed[cur[vi]]>=tq.fi)
            uni(eu[cur[vi]],ev[cur[vi]],0),vi++;
        for(int&tv:tq.se.se)
            uni(eu[tv],ev[tv],1);
        ans[tq.se.fi.se]=sz[par(tq.se.fi.fi)];
        rb();
    }
    sort(all(change),[=](int&x,int&y){return ed[x]>ed[y];});
    int ai=0,bi=0;
    edge.clear();
    while(ai<(int)change.size()&&bi<(int)cur.size())
    {
        if(ed[change[ai]]>ed[cur[bi]])
            edge.eb(change[ai]),ai++;
        else
            edge.eb(cur[bi]),bi++;
    }
    while(ai<(int)change.size())
        edge.eb(change[ai]),ai++;
    while(bi<(int)cur.size())
        edge.eb(cur[bi]),bi++;
    for(int&t:ans)
        cout<<t<<'\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=0;i++<m;)
        cin>>eu[i]>>ev[i]>>ed[i],edge.eb(i);
    sort(all(edge),[=](int&x,int&y){return ed[x]>ed[y];});
    cin>>q;
    vector<pair<int,pi> >qv;
    while(q-->0)
    {
        int t,u,v;
        cin>>t>>u>>v;
        qv.eb(t,pi(u,v));
        if((int)qv.size()>siz)
            solve(qv);
    }
    if(!qv.empty())
        solve(qv);
    cout.flush();
    return 0;
}

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