Submission #250149

#	Time	Username	Problem	Language	Result	Execution time	Memory
250149		jeqcho	Bridges (APIO19_bridges)	C++17	13 / 100	146 ms	48376 KiB

bridges

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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second

int n,m;
int const N=1e3;
vi adj[N];
int const M=1e5;
tuple<int,int,int> bridge[M];
vi matrix[N][N];
bitset<N> vis;

int dfs(int now, int weight)
{
    if(vis[now])return 0;
    int ans=1;
    vis[now]=1;
    trav(chi,adj[now])
    {
        trav(wlimit, matrix[now][chi])
        {
            if(weight>wlimit)continue;
            ans += dfs(chi,weight);
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    int u,v,d;
    F0R(i,m)
    {
        cin>>u>>v>>d;
        --u; --v;
        adj[u].pb(v);
        adj[v].pb(u);
        matrix[u][v].pb(d);
        matrix[v][u].pb(d);
        bridge[i] = {u,v,sz(matrix[u][v])-1};
    }
    int q;
    cin>>q;
    int typ, bj, rj, sj, wj;
    int id;
    while(q--)
    {
        cin>>typ;
        if(typ==1)
        {
            cin>>bj>>rj;
            --bj;
            tie(u,v,id) = bridge[bj];
            matrix[u][v][id] = rj;
            matrix[v][u][id] = rj;
        }
        else
        {
            cin>>sj>>wj;
            vis.reset();
            --sj;
            cout<<dfs(sj,wj)<<'\n';
        }
    }
    return 0;
}

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