Submission #142684

#	Time	Username	Problem	Language	Result	Execution time	Memory
142684		Bodo171	Bridges (APIO19_bridges)	C++14	13 / 100	156 ms	11100 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 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;
    }
    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=b[i];
    }
    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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27