Submission #921243

#TimeUsernameProblemLanguageResultExecution timeMemory
921243BBart888Factories (JOI14_factories)C++14
15 / 100
401 ms159668 KiB
#include <cstdio> #include <iostream> #include <vector> #include <list> #include <string> #include <set> #include <map> #include <algorithm> #include <fstream> #include <cmath> #include <queue> #include <stack> #include <cassert> #include <cstring> #include <climits> #include <functional> #include <cstdlib> #include <complex> #include <array> #include <iomanip> #include <bitset> #include <unordered_map> #include <random> #define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);} using namespace std; const int MAXN = 2e5 + 111; using ll = long long; const int P = 31; const ll mod1 = 1e9 + 7; const ll mod2 = 998244353; using ld = long double; const ld EPS = 1e-5; using pii = pair<int, int>; typedef complex<ll> Point; int sz[MAXN]; int par[MAXN]; ll best[MAXN]; ll dis[MAXN][25]; vector<pair<int,ll>> adj[MAXN]; bool vis[MAXN]; int lev[MAXN]; int find_size(int v, int p) { if (vis[v]) return 0; sz[v] = 1; for (auto u : adj[v]) { if (u.first == p) continue; sz[v] += find_size(u.first, v); } return sz[v]; } int find_centroid(int v, int p, int n) { for (auto u : adj[v]) { if (u.first == p || vis[u.first]) continue; if (sz[u.first] > n / 2) return find_centroid(u.first, v, n); } return v; } void calc_it(int v, int p,int C) { for (auto u : adj[v]) { if (u.first == p || vis[u.first]) continue; dis[u.first][lev[u.first] - lev[C]] = dis[v][lev[v] - lev[C]] + u.second; calc_it(u.first, v, C); } } void decompose2(int v, int p) { find_size(v, v); int c = find_centroid(v, v, sz[v]); vis[c] = true; calc_it(c, p, c); for (auto u : adj[c]) { if (u.first == p || vis[u.first]) continue; decompose2(u.first, c); } } void decompose1(int v, int p) { find_size(v, v); int c = find_centroid(v, v, sz[v]); vis[c] = true; par[c] = p; if (p != -1) lev[c] = lev[p] + 1; for (auto u : adj[c]) { if (u.first == p || vis[u.first]) continue; decompose1(u.first, c); } } void Init(int n, int a[], int b[], int d[]) { for (int i = 0; i < n - 1; i++) { adj[a[i] + 1].push_back(make_pair(b[i] + 1, d[i])); adj[b[i] + 1].push_back(make_pair(a[i] + 1, d[i])); } fill(best, best + MAXN, 1e18); decompose1(1, -1); fill(vis, vis + MAXN, false); decompose2(1, -1); } ll Query(int s, int x[], int t, int y[]) { ll ans = 1e18; for (int i = 0; i < s; i++) x[i]++; for (int i = 0; i < t; i++) y[i]++; for (int i = 0; i < s; i++) { int a = x[i]; int j = 0; while (a != -1) { best[a] = min(best[a], dis[x[i]][j]); j++; a = par[a]; } } for (int i = 0; i < t; i++) { int b = y[i]; int j = 0; while (b != -1) { ans = min(ans, best[b] + dis[y[i]][j]); j++; b = par[b]; } } for (int i = 0; i < s; i++) { int a = x[i]; while (a != -1) { best[a] = 1e18; a = par[a]; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...