제출 #553670

#제출 시각아이디문제언어결과실행 시간메모리
553670LucaDantas공장들 (JOI14_factories)C++17
0 / 100
38 ms48512 KiB
// Recodando pra lembrar virtual tree #include "factories.h" #include <bits/stdc++.h> using namespace std; constexpr int maxn = 5e5+10, logn = 21; constexpr long long inf = 0x3f3f3f3f3f3f3f3f; vector<pair<int,long long>> g[maxn]; int in[maxn], pai[logn][maxn], profundidade[maxn], t, n; long long depth[maxn]; void dfs(int u) { in[u] = ++t; for(auto [v, w] : g[u]) { if(v == pai[u][0]) continue; pai[v][0] = u; profundidade[v] = profundidade[u] + 1; depth[v] = depth[u] + w; dfs(v); } } void build_binary_lifting() { for(int l = 1; l < logn; l++) for(int i = 1; i <= n; i++) pai[i][l] = pai[pai[i][l-1]][l-1]; } int LCA(int a, int b) { if(profundidade[a] < profundidade[b]) swap(a, b); for(int l = logn-1; l >= 0; l--) if(profundidade[a] - (1<<l) >= profundidade[b]) a = pai[a][l]; if(a == b) return a; for(int l = logn-1; l >= 0; l--) if(pai[a][l] != pai[b][l]) a = pai[a][l], b = pai[b][l]; return pai[a][0]; } vector<pair<int, long long>> vt[maxn]; void get_vt(vector<int>& v) { sort(v.begin(), v.end(), [](int a, int b) { return in[a] < in[b]; }); int tam = v.size(); for(int i = 1; i < tam; i++) v.push_back(LCA(v[i-1], v[i])); sort(v.begin(), v.end(), [](int a, int b) { return in[a] < in[b]; }); v.erase(unique(v.begin(), v.end()), v.end()); for(int x : v) vt[x].clear(); for(int i = 1; i < v.size(); i++) { int lca = LCA(v[i-1], v[i]); long long DIST = depth[v[i]] - depth[lca]; vt[lca].push_back({v[i], DIST}); vt[v[i]].push_back({lca, DIST}); } // sort(v.begin(), v.end(), [](const int& a, const int& b) { return in[a] < in[b]; }); // int sz = (int)v.size(); // for(int i = 1; i < sz; i++) // v.push_back(LCA(v[i], v[i-1])); // sort(v.begin(), v.end(), [](const int& a, const int& b) { return in[a] < in[b]; }); // v.erase(unique(v.begin(), v.end()), v.end()); // for(int x : v) // vt[x].clear(); // for(int i = 1; i < (int)(v.size()); i++) { // int lca = LCA(v[i], v[i-1]); // long long d = depth[v[i]] - depth[lca]; // vt[v[i]].push_back({lca, d}); // vt[lca].push_back({v[i], d}); // } } void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) { n = N; for(int i = 0; i < n-1; i++) { A[i]++, B[i]++; g[A[i]].push_back({B[i], D[i]}), g[B[i]].push_back({A[i], D[i]}); } profundidade[1] = 1; depth[1] = 1; dfs(1); build_binary_lifting(); } long long dd[maxn]; bool mark[maxn]; long long dijkstra(const vector<int>& tudo, const vector<int>& X, const vector<int>& Y) { static priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> q; for(int x : tudo) dd[x] = inf, mark[x] = 0; for(int x : Y) dd[x] = 0, q.push({0, x}); while(q.size()) { int u = q.top().second; q.pop(); if(mark[u]) continue; mark[u] = 1; for(auto [v, w] : vt[u]) if(dd[v] > dd[u] + w) dd[v] = dd[u] + w, q.push({dd[v], v}); } long long ans = inf; for(int x : X) ans = min(ans, dd[x]); return ans; } long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) { vector<int> v, x, y; for(int i = 0; i < S; i++) v.push_back(X[i]+1), x.push_back(X[i]+1); for(int i = 0; i < T; i++) v.push_back(Y[i]+1), y.push_back(Y[i]+1); get_vt(v); return dijkstra(v, x, y); }

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

factories.cpp: In function 'void get_vt(std::vector<int>&)':
factories.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 1; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...