Submission #983535

#	Time	Username	Problem	Language	Result	Execution time	Memory
983535		horezushol	Bridges (APIO19_bridges)	C++14	13 / 100	168 ms	1372 KiB

bridges

#include<bits/stdc++.h>
#define len(x) ((x).size())

using namespace std;
using ll = long long;
const char nl = '\n';

const ll N = 2000;
ll n, m, q;

multiset<pair<ll, pair<ll, ll>>> g[N];

ll res = 0;
bool visited[N];
void dfs(ll x, ll w) {
  visited[x] = true;
  res ++;
  for (auto el : g[x]) {
    if (!visited[el.first] && w <= el.second.first) {
      dfs(el.first, w);
    }
  }
}

void rout() {
  for (ll i = 1; i <= n; i ++) {
    cout << i << ": ";
    for (auto el : g[i]) {
      cout << "{" << el.first << ", " << el.second.first << ", " << el.second.second << "} ";
    }
    cout << nl;
  }  
  cout << nl << nl;
}

void solve() {
  cin >> n >> m;
  for (ll i = 0, br = 1; i < m; i ++, br ++) {
    ll u, v, w;
    cin >> u >> v >> w;
    g[u].insert({v, {w, br}});
    g[v].insert({u, {w, br}});
  }
  ll q; cin >> q;
  while (q --) {
    ll t; cin >> t;
    if (t == 1) {
      ll b, r;
      cin >> b >> r;
      for (ll i = 1; i <= n; i ++) {
        for (auto el : g[i]) {
          if (el.second.second == b) {
            auto it = g[i].find(el);
            g[i].insert({el.first, {r, el.second.second}});
            g[i].erase(it);
            break;
          }
        }
      }
      // rout();
    } else {
      ll s, w;
      cin >> s >> w;
      dfs(s, w);
      // cout << s << " " << w << " ";
      cout << res << nl;
      // rout();
      for (ll i = 0; i <= n; i ++) {
        visited[i] = false;
      }
      res = 0;
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll tst = 1;
  // cin >> tst;
  while (tst --) {
    solve();
    cout << nl;
  }
}

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