제출 #252416

#제출 시각아이디문제언어결과실행 시간메모리
252416Erkhemkhuu다리 (APIO19_bridges)C++17
13 / 100
185 ms31860 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define F first #define S second typedef pair <ll, ll> pll; const ll sN = 1005; const ll N = 100005; bool vis[N]; vector <vector <ll> > adj(N); ll tree[N * 4], sz[N], par[N], out[N]; tuple <ll, ll, ll> brid[N]; vector <ll> wp[sN][sN]; struct trio { ll v, u, w; } edges[N]; struct trio1 { ll v, w, ind; } queries[N]; bool comp(trio &a, trio &b) { return (a.w > b.w); } bool comp1(trio1 &a, trio1 &b) { return (a.w > b.w); } void build(ll node, ll l, ll r) { if(l == r) { tree[node] = edges[l].w; return; } ll mid = (l + r) / 2; build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r); tree[node] = min(tree[node * 2], tree[node * 2 + 1]); return; } void update(ll node, ll l, ll r, ll idx, ll val) { if(l == r) { tree[node] = val; return; } ll mid = (l + r) / 2; if(l <= idx && idx <= mid) update(node * 2, l, mid, idx, val); else update(node * 2 + 1, mid + 1, r, idx, val); tree[node] = min(tree[node * 2], tree[node * 2 + 1]); return; } ll get(ll x) { return ((x == par[x]) ? (x) : (par[x] = get(par[x]))); } bool unite(ll v, ll u) { ll parv = get(v); ll paru = get(u); if(parv == paru) return false; if(sz[parv] < sz[paru]) swap(parv, paru); sz[parv] += sz[paru]; par[paru] = parv; return true; } void init() { for(ll i = 0; i < N; i++) { sz[i] = 1; par[i] = i; } return; } ll dfs(ll v, ll w) { ll ans = 1; vis[v] = true; for(auto &u: adj[v]) for(auto &x: wp[v][u]) if(!vis[u] && w <= x) ans += dfs(u, w); return ans; } int main() { ll n, m, i, v, u, w, q, t, l, r; bool flag = true; cin >> n >> m; flag &= (m != n - 1); for(i = 1; i <= m; i++) { cin >> v >> u >> w; adj[v].pb(u); adj[u].pb(v); flag &= (u == i + 1 && v == i); if(n <= 1000 && m <= 1000) { wp[v][u].pb(w); wp[u][v].pb(w); brid[i] = {v, u, wp[v][u].size() - 1}; } edges[i] = {v, u, w}; } cin >> q; if(n <= 1000 && m <= 1000 && q <= 10000) { while(q--) { cin >> t >> l >> r; if(t == 1) { auto temp = brid[l]; ll x = get <0> (temp); ll y = get <1> (temp); ll z = get <2> (temp); wp[x][y][z] = wp[y][x][z] = r; } else { memset(vis, false, sizeof(vis)); cout << dfs(l, r) << "\n"; } } return 0; } else { bool flag1 = true; cin >> q; for(i = 1; i <= q; i++) { cin >> t >> l >> r; queries[i] = {l, r, i}; flag1 &= (t == 2); } if(!flag1) return 0; for(i = 1; i <= n; i++) { par[i] = i; sz[i] = 1; } sort(edges + 1, edges + m + 1, comp); sort(queries + 1, queries + q + 1, comp1); ll cur = 1; for(i = 1; i <= q; i++) { while(cur <= n && edges[cur].w >= queries[i].w) { unite(edges[cur].v, edges[i].u); cur++; } out[queries[i].ind] = sz[get(queries[i].v)]; } for(i = 1; i <= q; i++) cout << out[i] << "\n"; } /* if(flag) { build(1, 1, n); while(q--) { cin >> t >> l >> r; if(t == 1) update(1, 1, n, l, r); else { } } return 0; } */ return 0; }
#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...