Submission #821597

#TimeUsernameProblemLanguageResultExecution timeMemory
821597mgl_diamondBridges (APIO19_bridges)C++17
13 / 100
3059 ms9824 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
template<class T> using vec = vector<T>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"
 
void setIO(string name="") {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".in", "r")) {
    freopen(file".in", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 5e4+5;

struct Edge {
  int u, v, w;
  Edge(int _u=0, int _v=0, int _w=0) : u(_u), v(_v), w(_w) {}
};

int n, m, q, cnt, vi[N];
vec<Edge> e;
vec<int> adj[N];

void dfs(int u, int k) {
  vi[u] = 1;
  cnt += 1;
  fore(i, adj[u]) {
    int v = e[i].u ^ e[i].v ^ u;
    if (vi[v] || e[i].w < k) continue;
    dfs(v, k);
  }
}

int main() {
  setIO();

  cin >> n >> m;
  foru(i, 0, m-1) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back(i);
    adj[v].push_back(i);
    e.emplace_back(u, v, w);
  }

  cin >> q;
  foru(i, 1, q) {
    int t;
    cin >> t;
    if (t == 1) {
      int edge, w;
      cin >> edge >> w;
      e[edge-1].w = w;
    }
    else {
      int node, w;
      cin >> node >> w;
      foru(i, 1, n) vi[i] = 0;
      cnt = 0;
      dfs(node, w);
      cout << cnt << "\n";
    }
  }
}

Compilation message (stderr)

bridges.cpp: In function 'void setIO(std::string)':
bridges.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...