Submission #348822

#	Time	Username	Problem	Language	Result	Execution time	Memory
348822		denkendoemeer	Bridges (APIO19_bridges)	C++14	73 / 100	3026 ms	48452 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int A=1<<16,B=1<<17;
int nex[A],sz[A];
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[B],y[B],w[B],ord[B];
short t[B];
int b[B],c[B];
int ans[B];
bool ok[B];
vector<int>ced;
vector<tuple<int,int,int>>query;
vector<pair<int,int>>we[B];
int cmp(int x,int y)
{
    return w[x]>w[y];
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    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)){
        fill(nex,nex+n,-1);
        fill(sz,sz+n,1);
        fill(ok,ok+m,0);
        ced.clear();
        query.clear();
        iota(ord,ord+m,0);
        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])
            cout<<ans[i]<<'\n';
return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:84:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |         for(auto &[a,b,c]:query){
      |                   ^
bridges.cpp:93: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]
   93 |                 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