Submission #712538

#	Time	Username	Problem	Language	Result	Execution time	Memory
712538		HuyQuang_re_Zero	Bridges (APIO19_bridges)	C++17	100 / 100	2926 ms	15016 KiB

bridges

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 400002
#define II pair <int,int>
#define fst first
#define snd second
using namespace std;
set <II> done;
II edge[N];
vector <II> roll;
struct pt { int lb,x,k; };
pt even[N];
struct Edge { int u,v,k; };
Edge bri[N];
int n,m,q,i,u,v,sz[N],r[N],updated[N],cur[N],res[N];
int root(int u) { return (u==r[u]) ? u : root(r[u]); }
void join(int u,int v)
{
    if(u==v) return ;
    if(sz[u]>sz[v]) swap(u,v);
    r[u]=v; sz[v]+=sz[u];
}
void roll_back()
{
    reverse(roll.begin(),roll.end());
    for(II a:roll) r[a.fst]=a.fst,sz[a.fst]=a.snd;
}
void solve(int l,int r)
{
    vector <pt> change,qr;
    for(i=l;i<=r;i++)
        if(even[i].lb==1)
        {
            if(updated[even[i].x]==1) continue;
            updated[even[i].x]=1;
            done.erase({ bri[even[i].x].k,even[i].x });
            change.push_back({ l-1,even[i].x,bri[even[i].x].k });
        }
        else qr.push_back({ i,even[i].x,even[i].k });
    for(i=l;i<=r;i++)
        if(even[i].lb==1) change.push_back({ i,even[i].x,even[i].k }),bri[even[i].x].k=even[i].k;
    sort(qr.begin(),qr.end(),[&](pt a,pt b){ return a.k>b.k;  });
    reverse(change.begin(),change.end());
    int cnt=0;
    for(auto tg:done) edge[++cnt]=tg;
    int j=cnt;
    for(auto tg:qr)
    {
        while(j>0 && edge[j].fst>=tg.k)
        {
            join(root(bri[edge[j].snd].u),root(bri[edge[j].snd].v));
            j--;
        }
        roll.clear();
        for(auto a:change)
        {
            if(a.lb>tg.lb || cur[a.x]==tg.lb) continue;
            cur[a.x]=tg.lb;
            if(a.k<tg.k) continue;
            int u=root(bri[a.x].u),v=root(bri[a.x].v);
            if(u!=v)
            {
                if(sz[u]>sz[v]) swap(u,v);
                roll.push_back({ u,sz[u] });
                roll.push_back({ v,sz[v] });
                join(u,v);
            }
        }
        int u=root(tg.x);
        res[tg.lb]=sz[u];
        roll_back();
    }
    for(auto tg:change)
    {
        if(updated[tg.x]==0) continue;
        updated[tg.x]=0;
        done.insert({ tg.k,tg.x });
    }
}
int main()
{
  //  freopen("ntu.inp","r",stdin);
   // freopen("ntu.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>bri[i].u>>bri[i].v>>bri[i].k,even[i].k,even[i]={ 1,i,bri[i].k };
    cin>>q;
    for(i=m+1;i<=m+q;i++) cin>>even[i].lb>>even[i].x>>even[i].k;
    for(i=1;i<=m;i++) done.insert({ even[i].k,i });
    int can=trunc(sqrt(q));
    for(int l=m+1;l<=m+q;l+=can)
    {
        for(u=1;u<=n;u++) r[u]=u,sz[u]=1;
        solve(l,min(l+can-1,m+q));
    }
    for(i=m+1;i<=m+q;i++)
        if(even[i].lb==2) cout<<res[i]<<'\n';
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:88:65: warning: right operand of comma operator has no effect [-Wunused-value]
   88 |     for(i=1;i<=m;i++) cin>>bri[i].u>>bri[i].v>>bri[i].k,even[i].k,even[i]={ 1,i,bri[i].k };
      |                                                         ~~~~~~~~^

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