| c++ competetive progamming |
| 1 | void dfs(ll v) { tin[v] = t++; for (auto u : g[v]) if (!used[u]) { dfs(u); } tout[v] = t; } |
| 2 | ll tin[maxn], tout[maxn]; ll t = 0; |
| 3 | using namespace std; using ll = long long; |
| 4 | #include <iostream> #include <vector> #include <algorithm> |
| 5 | #pragma GCC target("avx2") |
| 6 | vector<vector<ll>> g; |
| 7 | vector<bool> visited; |
| 8 | for (ll i = 0; i < n - 1; i++) { ll v, u; cin >> v >> u; v--; u--; g[v].push_back(u); g[u].push_back(v); } |
| 9 | dfs(0); |
| 10 | if (t) { cout << "YES "; else { cout << "NO "; } |
| 11 | queue<int> q; q.push(s); vector<int> dist(n, -1), p(n); dist[s] = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (int u : g[v]) { if (dist[u] == -1) { q.push(u); dist[u] = dist[v] + 1; p[u] = v; } } } |
| 12 | vector<int> dijkstra(int s) { vector<int> dist(n, inf), a(n, 0); dist[s] = 0; for (int i = 0; i < n; i++) { int v = -1; for (int u = 0; u < n; u++) if (!a[u] && (v == -1 || dist[u] < dist[v])) v = u; a[v] = true; for (auto [u, w] : g[v]) dist[u] = min(d[u], d[v] + w); } return dist; } |
| 13 | void update(ll v, ll vl, ll vr, ll i, ll x) { if (vl == vr) { t[v] = x; return; } ll m = (vl + vr) / 2; if (i <= m) { update(v * 2, vl, m, i, x); } else { update(v * 2 + 1, m + 1, vr, i, x); } t[v] = t[v * 2] + t[v * 2 + 1]; } ll get(ll v, ll vl, ll vr, ll l, ll r) { if (vl > r || vr < l) { return 0; } if (vl >= l && vr <= r) { return t[v]; } ll m = (vl + vr) / 2; return get(2 * v, vl, m, l, r) + get(2 * v + 1, m + 1, vr, l, r); } |
Комментарии