Submission #1098332

#TimeUsernameProblemLanguageResultExecution timeMemory
1098332vjudge1Bridges (APIO19_bridges)C++17
13 / 100
3051 ms7172 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct B { int u, v, d; }; struct Q { int t, x, y; }; class UF { public: vector<int> p, r, sz; UF(int n) { p.resize(n); r.resize(n, 0); sz.resize(n, 1); for (int i = 0; i < n; ++i) p[i] = i; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void unite(int x, int y) { int rx = find(x); int ry = find(y); if (rx != ry) { if (r[rx] > r[ry]) { p[ry] = rx; sz[rx] += sz[ry]; } else if (r[rx] < r[ry]) { p[rx] = ry; sz[ry] += sz[rx]; } else { p[ry] = rx; r[rx]++; sz[rx] += sz[ry]; } } } int component_size(int x) { return sz[find(x)]; } }; int main() { int n, m; cin >> n >> m; vector<B> bs(m); for (int i = 0; i < m; ++i) { cin >> bs[i].u >> bs[i].v >> bs[i].d; bs[i].u--; bs[i].v--; } int q; cin >> q; vector<Q> qs(q); vector<int> res; for (int i = 0; i < q; ++i) { cin >> qs[i].t >> qs[i].x >> qs[i].y; qs[i].x--; // Сокращение на 1 в обоих случаях } for (int i = 0; i < q; ++i) { if (qs[i].t == 1) { bs[qs[i].x].d = qs[i].y; } else { int car_w = qs[i].y; int start = qs[i].x; UF uf(n); for (int j = 0; j < m; ++j) { if (bs[j].d >= car_w) { uf.unite(bs[j].u, bs[j].v); } } res.push_back(uf.component_size(start)); } } for (int r : res) { cout << r << endl; } 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...