제출 #732983

#제출 시각아이디문제언어결과실행 시간메모리
732983Magikarp4000다리 (APIO19_bridges)C++17
13 / 100
3073 ms28824 KiB
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e5+1;
int n,m,q;
UM<int,vector<int>> v[MAXN];
vector<pair<PII,PII>> e;
bool z[MAXN];

signed main() {
    OPTM;
    cin >> n >> m;
    FOR(i,0,m) {
        int a,b,w; cin >> a >> b >> w;
        v[a][b].PB(w);
        v[b][a].PB(w);
        e.PB({{a,b},{v[a][b].size()-1,v[b][a].size()-1}});
    }
    cin >> q;
    FOR(i,0,q) {
      int t; cin >> t;
      if (t == 1) {
        int idx,w; cin >> idx >> w;
        idx--;
        int a = e[idx].F.F, b = e[idx].F.S, c = e[idx].S.F, d = e[idx].S.S;
        v[a][b][c] = v[b][a][d] = w;
      }
      else {
        int s,w; cin >> s >> w;
        FOR(i,1,n+1) z[i] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
          int k = q.front(); q.pop();
          if (z[k]) continue;
          z[k] = 1;
          FORX(u,v[k]) {
            FORX(y,u.S) if (y >= w) q.push(u.F);
          }
        }
        int res = 0;
        FOR(i,1,n+1) res += z[i];
        cout << res << ln;
      }
    }
}
#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...