Submission #142686

#	Time	Username	Problem	Language	Result	Execution time	Memory
142686		Bodo171	Bridges (APIO19_bridges)	C++14	43 / 100	917 ms	12500 KiB

bridges

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=100005;
struct evn
{
    int t,a,b;
}ev[2*nmax];
bool comp(evn unu,evn doi)
{
    if(unu.t==doi.t) return unu.a>doi.a;
    return unu.t>doi.t;
}
vector<int> v[nmax];
int a[nmax],b[nmax],c[nmax];
int viz[nmax],tt[nmax],rg[nmax],an[nmax];
bool path;
int n,m,i,q,tip,x,y;
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
void dfs(int x,int lim)
{
    int y;
    viz[x]=1;
    for(int i=0;i<v[x].size();i++)
        if(c[v[x][i]]>=lim)
    {
        y=(a[v[x][i]]^b[v[x][i]]^x);
        if(!viz[y])
            dfs(y,lim);
    }
}
int finds(int x)
{
    while(x!=tt[x])
        x=tt[x];
    return x;
}
void unite(int A,int B)
{
    if(A==B) return;
    if(rg[A]<rg[B]) swap(A,B);
    rg[A]+=rg[B];tt[B]=A;
}
int arb[4*nmax];
void update(int nod,int l,int r,int poz,int val)
{
    if(l==r)
    {
        arb[nod]=val;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m,poz,val);
    else update(2*nod+1,m+1,r,poz,val);
    arb[nod]=min(arb[2*nod],arb[2*nod+1]);
}
int mn;
void query(int nod,int l,int r,int st,int dr)
{
    if(st<=l&&r<=dr)
    {
        mn=min(mn,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m,st,dr);
    if(m<dr)  query(2*nod+1,m+1,r,st,dr);
}
int Q(int S,int D)
{
    mn=(1<<30);
    query(1,1,n,S,D);
    return mn;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    path=(m==n-1);
    for(i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
        path&=((abss(a[i]-b[i])==1));
    }
    dfs(1,0);
    for(i=1;i<=n;i++)
        path&=(viz[i]);
    cin>>q;
    if(n<=1000&&m<=1000&&q<=10000)
    {
        for(int cnt=1;cnt<=q;cnt++)
        {
            cin>>tip;
            if(tip==1)
            {
                cin>>x>>y;
                c[x]=y;
            }
            else
            {
                cin>>x>>y;
                for(i=1; i<=n; i++)
                    viz[i]=0;
                dfs(x,y);
                int ans=0;
                for(i=1; i<=n; i++)
                    ans+=viz[i];
                cout<<ans<<'\n';
            }
        }
        return 0;
    }
    if(path)
    {
        for(i=1;i<=n-1;i++)
        {
            update(1,1,n,min(a[i],b[i]),c[i]);
        }
        for(int cnt=1;cnt<=q;cnt++)
        {
            cin>>tip;
            if(tip==1)
            {
                cin>>x>>y;
                update(1,1,n,min(a[x],b[x]),y);
            }
            else
            {
                cin>>x>>y;
                int st=x,dr=x;
                for(int p=17;p>=0;p--)
                    if(st-(1<<p)>=1&&Q(st-(1<<p),x-1)>=y)
                       st-=(1<<p);
                for(int p=17;p>=0;p--)
                    if(dr+(1<<p)<=n&&Q(x,dr+(1<<p)-1)>=y)
                       dr+=(1<<p);
                cout<<dr-st+1<<'\n';
            }
        }
        return 0;
    }
    for(i=1;i<=m;i++)
    {
        ev[i].t=c[i];
        ev[i].a=a[i],ev[i].b=b[i];
    }
    for(i=1;i<=q;i++)
    {
        cin>>tip>>x>>y;
        ev[m+i].t=y;
        ev[m+i].a=-i;ev[m+i].b=x;
    }
    sort(ev+1,ev+m+q+1,comp);
    for(i=1;i<=n;i++)
        tt[i]=i,rg[i]=1;
    for(i=1;i<=m+q;i++)
    {
        if(ev[i].a<0)
        {
            an[-ev[i].a]=rg[finds(ev[i].b)];
        }
        else
        {
            unite(finds(ev[i].a),finds(ev[i].b));
        }
    }
    for(i=1;i<=q;i++)
        cout<<an[i]<<'\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

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