Submission #404945

#	Time	Username	Problem	Language	Result	Execution time	Memory
404945		A_D	Bridges (APIO19_bridges)	C++14	13 / 100	93 ms	116056 KiB

bridges

#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
const int N=1e3+100;
bool vis[N];
multiset<int> a[N][N];
int u[N];
int v[N];
int w[N];
vector<int> g[N];
int ans;
void dfs(int u,int w)
{
    ans++;
    vis[u]=1;
    for(auto x:g[u]){
        if(vis[x])continue;
        if(a[u][x].empty())continue;
        int q=*a[u][x].rbegin();
        if(q>=w)dfs(x,w);
    }
}
void solve()
{
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
        a[u[i]][v[i]].insert(w[i]);
        a[v[i]][u[i]].insert(w[i]);
    }
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int i,nw;
            cin>>i>>nw;
            a[u[i]][v[i]].erase(a[u[i]][v[i]].find(w[i]));
            a[v[i]][u[i]].erase(a[v[i]][u[i]].find(w[i]));
            w[i]=nw;
            a[u[i]][v[i]].insert(w[i]);
            a[v[i]][u[i]].insert(w[i]);
        }
        else{
            ans=0;
            int u,w;
            cin>>u>>w;
            memset(vis,0,sizeof(vis));
            dfs(u,w);
            cout<<ans<<endl;
        }
    }
}

main()
{
    int t=1;
    //cin>>t;
    while(t--)solve();
}

Compilation message (stderr)

bridges.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main()
      | ^~~~

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