Submission #347896

#	Time	Username	Problem	Language	Result	Execution time	Memory
347896		denkendoemeer	Bridges (APIO19_bridges)	C++14	73 / 100	3034 ms	48624 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
int nex[1<<16],sz[1<<16];
stack<int>st;
int findt(int nod)
{
    if (nex[nod]<0)
        return nod;
    return findt(nex[nod]);
}
void onion(int x,int y)
{
    x=findt(x);
    y=findt(y);
    if (x==y){
        st.push(-1);
        return ;
    }
    if (sz[x]>sz[y])
        swap(x,y);
    nex[x]=y;
    sz[y]+=sz[x];
    st.push(x);
}
void undo()
{
    int x=st.top();
    st.pop();
    if (x<0)
        return ;
    sz[nex[x]]-=sz[x];
    nex[x]=-1;
}
int x[1<<17],y[1<<17],w[1<<17],ord[1<<17];
short t[1<<17];
int b[1<<17],c[1<<17];
int ans[1<<17];
bool ok[1<<17];
vector<int>ced;
vector<tuple<int,int,int>>query;
vector<pair<int,int>>we[1<<17];
int cmp(int x,int y)
{
    return w[x]>w[y];
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,i;
    cin>>n>>m;
    for(i=0;i<m;i++)
        cin>>x[i]>>y[i]>>w[i],x[i]--,y[i]--;
    int q;
    cin>>q;
    for(i=0;i<q;i++)
        cin>>t[i]>>b[i]>>c[i],t[i]--,b[i]--;
    int st=0,dr=0;
    dr=min(dr+1024,q);
    for(;st<q;st=st+1024,dr=min(st+1024,q)){
        for(i=0;i<n;i++)
            nex[i]=-1,sz[i]=1;
        for(i=0;i<m;i++)
            ok[i]=0;
        ced.clear();
        query.clear();
        for(i=0;i<m;i++)
            ord[i]=i;
        sort(ord,ord+m,cmp);
        for(i=st;i<dr;i++)
            if (t[i])
                query.emplace_back(c[i],b[i],i);
            else
                ok[b[i]]=1;
        for(i=0;i<m;i++)
            if (ok[i])
                we[i]={{w[i],0}},ced.push_back(i);
        for(i=st;i<dr;i++)
            if (t[i]==0)
                we[b[i]].push_back({c[i],i});
        sort(query.rbegin(),query.rend());
        int aux=0;
        for(auto &[a,b,c]:query){
            while(aux<m && a<=w[ord[aux]]){
                if (ok[ord[aux]]==0)
                    onion(x[ord[aux]],y[ord[aux]]);
                aux++;
            }
            int cnt=0;
            for(auto it2:ced){
                int num=0;
                while(num<we[it2].size() && we[it2][num].second<=c)
                    ++num;
                --num;
                if (num>=0 && a<=we[it2][num].first)
                    onion(x[it2],y[it2]),++cnt;
            }
            ans[c]=sz[findt(b)];
            while(cnt--)
                undo();
        }
        for(i=st;i<dr;i++)
            if (t[i]==0)
                w[b[i]]=c[i];
    }
    for(i=0;i<q;i++)
        if (t[i])
            printf("%d\n",ans[i]);
return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:83:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |         for(auto &[a,b,c]:query){
      |                   ^
bridges.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                 while(num<we[it2].size() && we[it2][num].second<=c)
      |                       ~~~^~~~~~~~~~~~~~~

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