Submission #1087132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087132		alexander707070	Bridges (APIO19_bridges)	C++14	13 / 100	116 ms	24640 KiB

bridges

#include<bits/stdc++.h>
#define MAXN 50007
using namespace std;

int n,m,q,a[MAXN],b[MAXN],c[MAXN];
int type[MAXN],s[MAXN],w[MAXN];

int cnt;
vector<int> weights;
unordered_map<int,int> mp;

vector< pair<int,int> > v[MAXN];

int tim,li[MAXN];

int dfs(int x,int w){
    li[x]=tim;

    int res=1;
    for(int i=0;i<v[x].size();i++){
        if(li[v[x][i].first]==tim or c[v[x][i].second]<w)continue;
        res+=dfs(v[x][i].first,w);
    }

    return res;
}

int main(){

    cin>>n>>m;

    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i];
        weights.push_back(c[i]);

        v[a[i]].push_back({b[i],i});
        v[b[i]].push_back({a[i],i});
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>type[i]>>s[i]>>w[i];
        weights.push_back(w[i]);
    }

    sort(weights.begin(),weights.end());
    for(int i=0;i<weights.size();i++){
        if(i==0 or weights[i]!=weights[i-1])cnt++;
        mp[weights[i]]=cnt;
    }

    for(int i=1;i<=m;i++)c[i]=mp[c[i]];
    for(int i=1;i<=q;i++)w[i]=mp[w[i]];

    for(int i=1;i<=q;i++){
        if(type[i]==1){
            c[s[i]]=w[i];
        }else{
            tim++;
            cout<<dfs(s[i],w[i])<<"\n";
        }
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int dfs(int, int)':
bridges.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<weights.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