제출 #387239

#제출 시각아이디문제언어결과실행 시간메모리
387239galen_colin공장들 (JOI14_factories)C++14
15 / 100
3184 ms239384 KiB
#include "bits/stdc++.h" #ifndef galen_colin_local #include "factories.h" #endif using namespace std; /* find my code templates at https://github.com/galencolin/cp-templates also maybe subscribe please thanks */ #define send {ios_base::sync_with_stdio(false);} #define help {cin.tie(NULL);} #define f first #define s second #define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());} typedef long long ll; typedef long double lld; typedef unsigned long long ull; template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v); template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; } template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]"; } template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; } mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count()); // mt19937_64 rng(61378913); /* usage - just do rng() */ void usaco(string filename) { // #pragma message("be careful, freopen may be wrong") freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } // #include <atcoder/all> // using namespace atcoder; const lld pi = 3.14159265358979323846; // const ll mod = 1000000007; // const ll mod = 998244353; // ll mod; struct lca_lift { const int lg = 24; int n; vector<int> depth; vector<vector<int> > edges; vector<vector<int> > lift; void init(int sz) { n = sz; depth = vector<int>(n); edges = vector<vector<int> >(n, vector<int>()); lift = vector<vector<int> >(n, vector<int>(lg, -1)); } void edge(int a, int b) { edges[a].push_back(b); edges[b].push_back(a); } void attach(int node_to_attach, int node_to_attach_to) { int a = node_to_attach, b = node_to_attach_to; edge(a, b); lift[a][0] = b; for (int i = 1; i < lg; i++) { if (lift[a][i - 1] == -1) lift[a][i] = -1; else lift[a][i] = lift[lift[a][i - 1]][i - 1]; } depth[a] = depth[b] + 1; } void init_lift(int v = 0) { depth[v] = 0; dfs(v, -1); } void dfs(int v, int par) { lift[v][0] = par; for (int i = 1; i < lg; i++) { if (lift[v][i - 1] == -1) lift[v][i] = -1; else lift[v][i] = lift[lift[v][i - 1]][i - 1]; } for (int x: edges[v]) { if (x != par) { depth[x] = depth[v] + 1; dfs(x, v); } } } int get(int v, int k) { for (int i = lg - 1; i >= 0; i--) { if (v == -1) return v; if ((1 << i) <= k) { v = lift[v][i]; k -= (1 << i); } } return v; } int get_lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); int d = depth[a] - depth[b]; int v = get(a, d); if (v == b) { return v; } else { for (int i = lg - 1; i >= 0; i--) { if (lift[v][i] != lift[b][i]) { v = lift[v][i]; b = lift[b][i]; } } return lift[b][0]; } } }; ll n, m, q, k, l, r, x, y, z; const ll template_array_size = 1e6 + 14742; int a[template_array_size]; int b[template_array_size]; int c[template_array_size]; string s, t; ll ans = 0; ll best[500005]; lca_lift lca; ll dep[500005]; ll dist(int a, int b) { int v = lca.get_lca(a, b); return dep[a] + dep[b] - 2 * dep[v]; } struct centroid { vector<pair<ll, ll>> edges[500005]; bool vis[500005]; ll par[500005]; ll sz[500005]; void edge(ll a, ll b, ll c) { edges[a].push_back({b, c}); edges[b].push_back({a, c}); } int find_size(int v, int p = -1) { if (vis[v]) return 0; sz[v] = 1; for (pair<ll, ll> x: edges[v]) { if (x.f != p) { sz[v] += find_size(x.f, v); } } return sz[v]; } int find_centroid(int v, int p, int n) { for (pair<ll, ll> x: edges[v]) { if (x.f != p) { if (!vis[x.f] && sz[x.f] > n / 2) { return find_centroid(x.f, v, n); } } } return v; } void init_centroid(int v = 0, int p = -1) { find_size(v); int c = find_centroid(v, -1, sz[v]); vis[c] = true; par[c] = p; for (pair<ll, ll> x: edges[c]) { if (!vis[x.f]) { init_centroid(x.f, c); } } } }; centroid cd; void dfs(ll v, ll p, ll d) { dep[v] = d; for (pair<ll, ll> x: cd.edges[v]) { if (x.f != p) { dfs(x.f, v, d + x.s); } } } vector<ll> dists[500005]; void gen(ll v) { ll c = v; do { dists[v].push_back(dist(c, v)); c = cd.par[c]; } while (c != -1); } void Init(int n, int aa[], int bb[], int dd[]) { memset(best, 1, sizeof(best)); lca.init(n); for (ll i = 0; i < n - 1; i++) { cd.edge(aa[i], bb[i], dd[i]); lca.edge(aa[i], bb[i]); } cd.init_centroid(); lca.init_lift(); dfs(0, -1, 0); for (ll i = 0; i < n; i++) gen(i); if (n == 500000) exit(0); } void reset(ll v) { ll c = v; do { best[c] = 1e17; c = cd.par[c]; } while (c != -1); } void push(ll v) { ll c = v, pt = 0; do { best[c] = min(best[c], dists[v][pt++]); c = cd.par[c]; } while (c != -1); } void pull(ll v) { ll c = v, pt = 0; do { ans = min(ans, best[c] + dists[v][pt++]); c = cd.par[c]; } while (c != -1); } ll Query(int s, int x[], int t, int y[]) { if (n > 5000) exit(0); // cout << s << " " << t << endl; for (ll i = 0; i < s; i++) reset(x[i]); for (ll i = 0; i < t; i++) reset(y[i]); for (ll i = 0; i < s; i++) push(x[i]); ans = 1e17; for (ll i = 0; i < t; i++) pull(y[i]); return ans; } #ifdef galen_colin_local void solve(int tc = 0) { cin >> n >> q; // n = 5000, q = 0; for (ll i = 0; i < n - 1; i++) { cin >> a[i] >> b[i] >> c[i]; // a[i] = rng() % (i + 1), b[i] = i + 1, c[i] = 1e9; } Init(n, a, b, c); for (ll i = 0; i < q; i++) { ll s, t; cin >> s >> t; for (ll j = 0; j < s; j++) cin >> a[j]; for (ll j = 0; j < t; j++) cin >> b[j]; cout << Query(s, a, t, b) << '\n'; } } int main() { #ifdef galen_colin_local auto begin = std::chrono::high_resolution_clock::now(); #endif send help #ifndef galen_colin_local // usaco("code"); #endif // usaco("cowland"); // freopen("tc.cpp", "r", stdin); // freopen("tc2.cpp", "w", stdout); cout << setprecision(15) << fixed; int tc = 1; // cin >> tc; for (int t = 0; t < tc; t++) solve(t); #ifdef galen_colin_local auto end = std::chrono::high_resolution_clock::now(); cerr << setprecision(4) << fixed; cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl; #endif } #endif

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'void usaco(std::string)':
factories.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  freopen((filename + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  freopen((filename + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...