Submission #142680

#	Time	Username	Problem	Language	Result	Execution time	Memory
142680		Bodo171	Bridges (APIO19_bridges)	C++14	13 / 100	88 ms	9820 KiB

bridges

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int a[nmax],b[nmax],c[nmax];
int viz[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 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;
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:20: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