Submission #911131

#	Time	Username	Problem	Language	Result	Execution time	Memory
911131		duckindog	Bridges (APIO19_bridges)	C++14	13 / 100	3024 ms	10320 KiB

bridges

// from duckindog wth depression
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int N = 1e5 + 10;
struct edge {
  int u, v, w;
  edge() : u(0), v(0), w(0) {}
  edge(int u, int v, int w) : u(u), v(v), w(w) {}
} ed[N];
int n, m;
vector<int> ad[N];
 
int f[N];
int sktra(int x, int mw) {
  memset(f, 63, sizeof f);
  using pii = pair<int, int>;
  priority_queue<pii, vector<pii>, greater<pii>> q;
  q.push({f[x] = 0, x});
  while (q.size()) {
    int d, pre; tie(d, pre) = q.top(); q.pop();
    if (d != f[pre]) continue;
    for (auto i : ad[pre]) {
      int u = ed[i].u, v = ed[i].v, w = ed[i].w;
      if (v == pre) swap(u, v);
 
      if (f[v] > d + w && w >= mw)
        q.push({f[v] = d + w, v});
    }
 
  }
 
  int cnt = 0;
  for (int i = 1; i <= n; ++i) cnt += (f[i] != f[0]);
  return cnt;
}
 
int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
 
  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    ed[i] = {u, v, w};
    ad[u].push_back(i);
    ad[v].push_back(i);
  }
 
  int q; cin >> q;
  while (q--) {
    int ty; cin >> ty;
    if (ty == 1) {
      int i, nw; cin >> i >> nw;
      ed[i].w = nw;
 
    } else {
      int s, w; cin >> s >> w;
 
      cout << sktra(s, w) << '\n';
 
    }
 
  }
 
}

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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