Submission #143046

#	Time	Username	Problem	Language	Result	Execution time	Memory
143046		JovanK26	Bridges (APIO19_bridges)	C++14	13 / 100	3070 ms	9128 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
struct bridge
{
    int a;
    int b;
    int d;
};
int n,m;
vector< pair<int,int> > v[50001];
bool vis[50001];
int cnt=1;
bridge edg[100001];
void dfs(int start,int w)
{
    vis[start]=1;
    //cout << start <<' ';
    for(int i=0;i<v[start].size();i++)
    {
        if(!vis[v[start][i].first] && w<=v[start][i].second)
        {
            dfs(v[start][i].first,w);
            cnt++;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int a,b,c;
    for(int i=0;i<m;i++)
    {
        cin >> a >> b >> c;
        a--;
        b--;
        edg[i].a=a;
        edg[i].b=b;
        edg[i].d=c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    int q;
    cin >> q;
    int type;
    int br,r;
    int s,w;
    for(int i=0;i<q;i++)
    {
        cin >> type;
        if(type==1)
        {
            cin >> br >> r;
            br--;
            //edg[br].d=r;
            int node1=edg[br].a;
            int node2=edg[br].b;
            //cout << node1 <<' '<<node2<<endl;
            for(int i=0;i<v[node1].size();i++)
            {
                if(v[node1][i].first==node2 && v[node1][i].second==edg[br].d)
                {
                    v[node1][i].second=r;
                    break;
                    //edg[br].d=r;
                }
            }
            for(int i=0;i<v[node2].size();i++)
            {
                if(v[node2][i].first==node1 && v[node2][i].second==edg[br].d)
                {
                    v[node2][i].second=r;
                    edg[br].d=r;
                    break;
                }
            }
        }
        else
        {
            memset(vis,0,sizeof(vis));
            /*for(int nd=0;nd<n;nd++)
            {
                vis[nd]=0;
            }
            */
            cnt=1;
            cin >> s >> w;
            s--;
            dfs(s,w);
           // cout << endl;
            cout << cnt <<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[start].size();i++)
                 ~^~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:62:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<v[node1].size();i++)
                         ~^~~~~~~~~~~~~~~~
bridges.cpp:71:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<v[node2].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