Submission #843460

#TimeUsernameProblemLanguageResultExecution timeMemory
843460adaawfFactories (JOI14_factories)C++14
100 / 100
4786 ms299812 KiB
/*#include "factories.h" #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define pii pair<int, int> #define vi vector<int> #define vll vector<ll> #define vvi vector<vi> #define vii vector<pii> #define isz(x) (int)x.size() using namespace std; const int mxN = 5e5 + 5; const ll oo = 1e18; int n; vector<vii> G; vi vtn; vector<vii> vt; ll dis[mxN]; pii sparse[19][mxN]; int timer, ecnt, ap[mxN], dep[mxN], cur[mxN], tin[mxN], tout[mxN]; void dfs(int v, int p) { tin[v] = ++timer; dep[v] = dep[p] + 1; sparse[0][++ecnt] = {dep[v], v}; ap[v] = ecnt; for(auto &[u, w] : G[v]) { if(u == p) continue; dis[u] = dis[v] + p; dfs(u, v); sparse[0][++ecnt] = {dep[v], v}; } tout[v] = ++timer; } void build_sparse() { for(int p = 1, i = 1; p << 1 <= ecnt; p <<= 1, ++i) for(int j = 1; j <= ecnt - (p << 1) + 1; ++j) sparse[i][j] = min(sparse[i - 1][j], sparse[i - 1][j + p]); } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int LCA(int u, int v) { int l = ap[u], r = ap[v]; if(l > r) swap(l, r); int len = r - l + 1, lg_len = __lg(len); return min(sparse[lg_len][l], sparse[lg_len][r - (1 << lg_len) + 1]).ss; } void Init(int N, int A[], int B[], int D[]) { n = N; G.resize(n); vt.resize(n); for(int i = 0; i < N - 1; ++i) { G[A[i]].emplace_back(B[i], D[i]); G[B[i]].emplace_back(A[i], D[i]); } dfs(0, 0); build_sparse(); } long long Query(int S, int X[], int T, int Y[]) { queue<pii> q; for(int i = 0; i < S; ++i) { cur[X[i]] = 1; q.emplace(X[i], 0); vtn.emplace_back(X[i]); } for(int i = 0; i < T; ++i) { cur[Y[i]] = 2; vtn.emplace_back(Y[i]); } sort(all(vtn), [&](int u, int v) { return tin[u] < tin[v]; }); for(int i = 0; i < S + T - 1; ++i) { vtn.emplace_back(LCA(vtn[i], vtn[i + 1])); } sort(all(vtn), [&](int u, int v) { return tin[u] < tin[v]; }); vtn.erase(unique(all(vtn)), vtn.end()); auto add_vt = [&](int u, int v, int w) { vt[u].emplace_back(v, w); vt[v].emplace_back(u, w); }; stack<int> s; for(int i = 0; i < isz(vtn); ++i) { while(not s.empty() && not is_ancestor(s.top(), vtn[i])) s.pop(); if(s.empty()) s.emplace(vtn[i]); else { add_vt(s.top(), vtn[i], dis[vtn[i]] - dis[s.top()]); s.emplace(vtn[i]); } } ll res = oo; auto dfs = [&](auto self, int v, int p) -> vll { vll cur_dis(2, oo); if(cur[v]) cur_dis[cur[v] - 1] = 0; for(auto &[u, w] : G[v]) { if(u == p) continue; vll tmp = self(self, u, v); for(int i = 0; i < 2; ++i) cur_dis[i] = min(cur_dis[i], tmp[i] + w); } res = min(res, accumulate(all(cur_dis), 0LL)); return cur_dis; }; dfs(dfs, vtn[0], 0); for(int i = 0; i < S; ++i) { cur[X[i]] = 0; vt[X[i]].clear(); } for(int i = 0; i < T; ++i) { cur[Y[i]] = 0; vt[Y[i]].clear(); } vtn.clear(); return res; }*/ #include "factories.h" #include <bits/stdc++.h> using namespace std; long long int f[500005]; int n, d[500005], tin[500005], b[2000005], l[2000005], z = 0; vector<int> gg[500005], g[500005]; int p[500005][20], pp[2000005][22]; void bfs(int x) { queue<int> q; q.push(x); p[x][0] = x; f[x] = d[x] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int j = 1; j <= 19; j++) { p[u][j] = p[p[u][j - 1]][j - 1]; if (p[u][j] == 0) break; } for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (d[u] + 1 < d[v]) { d[v] = d[u] + 1; f[v] = f[u] + gg[u][i]; p[v][0] = u; q.push(v); } } } } void dfs(int x, int p) { b[++z] = x; pp[z][0] = x; tin[x] = z; for (int w : g[x]) { if (w == p) continue; dfs(w, x); b[++z] = x; pp[z][0] = x; } b[++z] = x; pp[z][0] = x; } void Init(int N, int A[], int B[], int D[]) { n = N; for (int i = 0; i < 500000; i++) { f[i] = 999999999999999999; d[i] = n * 2; } for (int i = 0; i < n - 1; i++) { int u = A[i], v = B[i], w = D[i]; g[u].push_back(v); g[v].push_back(u); gg[u].push_back(w); gg[v].push_back(w); } bfs(0); dfs(0, -1); for (int i = 2; i <= 2000000; i++) l[i] = l[i / 2] + 1; for (int i = 1; (1 << i) <= z; i++) { for (int j = 1; j <= z - (1 << i) + 1; j++) { if (d[pp[j][i - 1]] < d[pp[j + (1 << (i - 1))][i - 1]]) pp[j][i] = pp[j][i - 1]; else pp[j][i] = pp[j + (1 << (i - 1))][i - 1]; } } } int lca(int u, int v) { int x = tin[u], y = tin[v]; if (y <= x) swap(x, y); int g = l[y - x + 1]; int h = pp[x][g], k = pp[y - (1 << g) + 1][g]; if (d[h] < d[k]) return h; return k; } long long int check(int u, int v) { return f[u] + f[v] - f[lca(u, v)] * 2; } long long int Query(int S, int X[], int T, int Y[]) { if (S > 100 && T > 100) { vector<long long int> ff(n, 999999999999999999); vector<bool> dda(n, 0), dd(n, 0); for (int i = 0; i < T; i++) { dda[Y[i]] = 1; } priority_queue<pair<long long int, long long int>> q; for (int i = 0; i < S; i++) { q.push({0, X[i]}); ff[X[i]] = 0; } while (!q.empty()) { int u = q.top().second; q.pop(); if (dd[u] == 1) continue; dd[u] = 1; if (dda[u] == 1) return ff[u]; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i], w = gg[u][i]; if (ff[u] + w < ff[v]) { ff[v] = ff[u] + w; q.push({-ff[v], v}); } } } } long long int res = 999999999999999999; for (int i = 0; i < S; i++) { for (int j = 0; j < T; j++) { res = min(res, check(X[i], Y[j])); } } return res; }

Compilation message (stderr)

factories.cpp: In function 'void bfs(int)':
factories.cpp:164:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (int i = 0; i < g[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:240:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |             for (int i = 0; i < g[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...