Submission #146634

#	Time	Username	Problem	Language	Result	Execution time	Memory
146634		Bodo171	Bridges (APIO19_bridges)	C++14	73 / 100	3045 ms	26076 KiB

bridges

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>
using namespace std;
const int nmax=100005;
const int buck=250;
struct event
{
    int tip,id,c;
}ev,evs[2*nmax+2*buck],niu[2*nmax+2*buck];
bool comp(event unu,event doi)
{
    if(unu.c==doi.c) return unu.tip>doi.tip;
    return unu.c<doi.c;
}
vector<int> spec,norm,mods;
vector<int> ad[nmax];
map<int,int> act;
int tt[nmax],rg[nmax],mic[nmax],mare[nmax],a[nmax],b[nmax],w[nmax],tip[nmax],wh[nmax],cost[nmax],ap[nmax],ans[nmax],ini[nmax],viz[nmax],ps[2*nmax];
int nxt[2*nmax],ce[2*nmax],cap[2*nmax];
int ops,n,m,q,i,nr,j,sum,lim,tot;
int finds(int x)
{
    int y=x,aux;
    while(x!=tt[x])
        x=tt[x];
    while(y!=x)
    {
        aux=tt[y];
        tt[y]=x;
        y=aux;
    }
    return x;
}
void unite(int A,int B)
{
    if(A==B) return;
    if(rg[A]<rg[B]) swap(A,B);
    tt[B]=A;rg[A]+=rg[B];
}
void baga(int a,int b)
{
    nxt[cap[a]]=++tot;
    cap[a]=tot;
    ce[tot]=b;
}
void add(int x,int y)
{
    baga(x,y);
    baga(y,x);
}
void res(int x)
{
    cap[x]=x;
    nxt[x]=0;
    viz[x]=0;
}
void dfs(int x)
{
    viz[x]=1;sum+=rg[x];
    for(int it=nxt[x];it!=0;it=nxt[it])
        if(!viz[ce[it]])
           dfs(ce[it]);
}
void mysort()
{
    for(i=1;i<=nr;i++)
        ps[evs[i].c]++;
    for(i=1;i<=lim;i++)
        ps[i]+=ps[i-1];
    for(i=1;i<=nr;i++)
        niu[++ps[evs[i].c-1]]=evs[i];
    for(i=0;i<=lim;i++)
        ps[i]=0;
}
int ch,num;
string str;
int getnum()
{
    num=0;
    while(str[ch]>='0'&&str[ch]<='9')
    {
        num=num*10+str[ch]-'0';
        ch++;
    }
    ch++;
    return num;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    getline(cin,str);ch=0;
    n=getnum();m=getnum();
    for(i=1;i<=m;i++)
    {
        getline(cin,str);ch=0;
        a[i]=getnum();b[i]=getnum();w[i]=getnum();
        norm.push_back(w[i]);
    }
     getline(cin,str);ch=0;
     q=getnum();
    for(i=1;i<=q;i++)
    {
        getline(cin,str);ch=0;
        tip[i]=getnum();wh[i]=getnum();cost[i]=getnum();
        norm.push_back(cost[i]);
    }
    sort(norm.begin(),norm.end());
    norm.erase(unique(norm.begin(),norm.end()),norm.end());
    lim=norm.size();
    for(i=0;i<norm.size();i++)
      act[norm[i]]=i+1;
    for(i=1;i<=m;i++)
        w[i]=act[w[i]];
    for(i=1;i<=q;i++)
        cost[i]=act[cost[i]];
    int bg=0;
    tot=n;
    for(i=1;i<=n;i++)
        cap[i]=i;
    for(bg=1;bg<=q;bg++)
    {
        nr=0;
        ops=0;
        spec.resize(0);mods.resize(0);
        for(i=1;i<=n;i++)
            tt[i]=i,rg[i]=1;
        for(i=bg;i<=q&&mods.size()<buck;i++)
        {
            if(tip[i]==1)
            {
                spec.push_back(wh[i]);
                ap[wh[i]]=1;
                ini[wh[i]]=w[wh[i]];
                mods.push_back(i);
            }
            else
            {
                evs[++nr]={1,i,cost[i]};
            }
        }
        i--;int en=i;
         for(i=1;i<=m;i++)
            if(!ap[i])
              evs[++nr]={0,i,w[i]};
        mysort();
        for(i=nr;i>=1;i--)
        {
            ev=niu[i];
            if(ev.tip==0)
                unite(finds(a[ev.id]),finds(b[ev.id]));
            else
            {
                int ind=ev.id;
                tot=n;
                for(j=0; j<mods.size()&&mods[j]<=ind; j++)
                    w[wh[mods[j]]]=cost[mods[j]];
                for(j=0; j<spec.size(); j++)
                    if(w[spec[j]]>=ev.c)
                        add(finds(a[spec[j]]),finds(b[spec[j]]));
                sum=0;
                dfs(finds(wh[ind]));
                ans[ind]=sum;
                res(finds(wh[ind]));
                for(j=0; j<spec.size(); j++)
                {
                    res(finds(a[spec[j]]));
                    res(finds(b[spec[j]]));
                    w[spec[j]]=ini[spec[j]];
                }
                for(int p=n+1;p<=tot;p++)
                    nxt[p]=ce[p]=0;
            }
        }
        for(i=bg;i<=en;i++)
           if(tip[i]==1)
              w[wh[i]]=cost[i];
        for(i=0;i<spec.size();i++)
            ap[spec[i]]=0;
        bg=en;
    }
    for(i=1;i<=q;i++)
        if(tip[i]==2)
         cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:115:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<norm.size();i++)
             ~^~~~~~~~~~~~
bridges.cpp:160:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0; j<mods.size()&&mods[j]<=ind; j++)
                          ~^~~~~~~~~~~~
bridges.cpp:162:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0; j<spec.size(); j++)
                          ~^~~~~~~~~~~~
bridges.cpp:169:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(j=0; j<spec.size(); j++)
                          ~^~~~~~~~~~~~
bridges.cpp:182:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<spec.size();i++)
                 ~^~~~~~~~~~~~

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