Submission #1044808

#TimeUsernameProblemLanguageResultExecution timeMemory
1044808vjudge1Bridges (APIO19_bridges)C++17
13 / 100
43 ms6056 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll mod = 1e9 + 7;
const ll N = 2e5 + 37;
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
const ll inf = (ll)2e18 + 37;
using aaa = array<int, 3>;
int n, m, Q;
vector<vector<array<int, 3> > > g;
vector<bool> vis;
int ans = 0, car = -1;
vector<int> change;
void brute_dfs(int v) {
  if(vis[v]) {
    return;
  }
  ++ans;
  vis[v] = true;
  for(auto& a : g[v]) {
    if(change[a[2]] != -1) {
      a[1] = change[a[2]];
    }
    if(car <= a[1] and !vis[a[0]]) {
      brute_dfs(a[0]);
    }
  }
}

void brute() {
  while(Q--) {
    ans = 0;
    int qt;
    cin >> qt;
    if(qt == 1) {
      int idx, w;
      cin >> idx >> w;
      change[idx] = w;
    }
    else if(qt == 2) {
      int u;
      cin >> u >> car;
      vis.assign(n + 1, false);
      brute_dfs(u);
      // cout << u << ' ' << car << ' ' << vis << " : " << ans << endl;
      cout << ans << endl;
    }
    else assert(false);
  }
}

void solve() {
  cin >> n >> m;
  g.assign(n + 1, vector<aaa>());
  change.assign(m + 1, -1);
  vis.assign(n + 1, false);
  for(int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    g[u].pb({v, c, i+1});
    g[v].pb({u, c, i+1});
  }
  cin >> Q;
  if(n <= 1000 and m <= 1000 and Q <= 10'000) {
    brute();
    return;
  }
}


signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // signed t; cin >> t; while(t--) 
    solve();
}

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}
 
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
#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...