Submission #347884

#	Time	Username	Problem	Language	Result	Execution time	Memory
347884		denkendoemeer	Bridges (APIO19_bridges)	C++14	14 / 100	2392 ms	47196 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
int nex[50005],sz[50005];
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[100005],y[100005],w[100005],ord[100005],t[100005],b[100005],c[100005];
int ans[100005];
bool ok[100005];
vector<int>ced;
struct nr
{
    int a,b,c;
};
vector<nr>query;
vector<pair<int,int>>we[100005];
int cmp(int x,int y)
{
    return w[x]>w[y];
}
int cmp2(nr x,nr y)
{
    if (x.a==y.a){
        if (x.b==y.b)
            return x.c<y.c;
        return x.b<y.b;
    }
    return x.a<y.a;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%d%d%d",&x[i],&y[i],&w[i]),x[i]--,y[i]--;
    int q;
    scanf("%d",&q);
    for(i=0;i<q;i++)
        scanf("%d%d%d",&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.push_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(),cmp2);
        int aux=0;
        for(auto it:query){
            while(aux<m && it.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<it.c)
                    ++num;
                --num;
                if (it.a<=we[it2][num].first)
                    onion(x[it2],y[it2]),++cnt;
            }
            ans[it.c]=sz[findt(it.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:103: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]
  103 |                 while(num<we[it2].size() && we[it2][num].second<it.c)
      |                       ~~~^~~~~~~~~~~~~~~
bridges.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         scanf("%d%d%d",&x[i],&y[i],&w[i]),x[i]--,y[i]--;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d%d%d",&t[i],&b[i],&c[i]),t[i]--,b[i]--;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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