| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 792164 |
2023-07-24T16:44:37 Z |
bane |
Factories (JOI14_factories) |
C++17 |
|
1878 ms |
158552 KB |
#include<bits/stdc++.h>
using namespace std;
#include "factories.h"
struct weighted_graph{
int N;
vector<vector<pair<long long,long long>>>adj, GC;
vector<long long>in, depth, crnci, dist, dp, sz;
vector<vector<int>>lift;
inline void dec(int _N){
N = _N;
adj.resize(N+1);
in.resize(N+1);
lift.resize(N+1);
depth.resize(N+1);
crnci.resize(N+1);
dist.resize(N+1);
GC.resize(N+1);
dp.resize(N+1);
sz.resize(N+1);
for (int i = 1; i <= N; i++){
dp[i] = (long long)1e18;
}
for (int i = 1; i <= N; i++){
lift[i].resize(20);
}
}
inline void add_edge(int A, int B, int D){
adj[A].push_back({B,D});
adj[B].push_back({A,D});
}
inline void init(){
int timer = 1;
function<int(int,int, long long h)>Dfs = [&](int u, int p, long long h){
in[u] = timer++;
depth[u] = depth[p] + 1;
sz[u] = 1;
dist[u] = h;
lift[u][0] = p;
for (auto& [x,w] : adj[u]){
if (x == p)continue;
sz[u] += Dfs(x,u, h + w);
}
return sz[u];
};
depth[1] = -1;
Dfs(1,1,0);
for (int i = 1; i < 20; i++){
for (int j = 1; j <= N; j++){
lift[j][i] = lift[lift[j][i-1]][i-1];
}
}
}
inline int LCA(int A, int B){
if (depth[A] > depth[B])swap(A,B);
int k = depth[B] - depth[A];
for (int i = 19; i>=0; i--){
if ((1 << i) & k){
B = lift[B][i];
}
}
if (A == B)
return A;
for (int i = 19; i>=0; i--){
if (lift[B][i] != lift[A][i]){
B = lift[B][i];
A = lift[A][i];
}
}
return lift[A][0];
}
inline int Dijkstra(vector<int>& sve){
priority_queue<pair<long long,int>>pq;
for (int i = 0; i < (int)sve.size(); i++){
if (crnci[sve[i]] == 2){
dp[sve[i]] = 0;
pq.push({0,sve[i]});
}
}
while(!pq.empty()){
int node = pq.top().second;
long long dst = -pq.top().first;
pq.pop();
if (dst != dp[node])continue;
if (crnci[node] == 1)return dst;
for (auto& [x,w] : GC[node]){
if (dp[x] > w + dst){
dp[x] = w + dst;
pq.push({-dp[x], x});
}
}
}
return -1;
}
inline int Query(int S, int X[], int T, int Y[]){
vector<int>sve;
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++){
sve.push_back(X[i]);
}
for (int i = 0; i < T; i++){
sve.push_back(Y[i]);
}
sort(sve.begin(),sve.end(), [&](int u, int p){
return in[u] < in[p];
});
for (int i = 1; i < S + T; i++){
sve.push_back(LCA(sve[i - 1], sve[i]));
}
sort(sve.begin(),sve.end(), [&](int u, int p){
return in[u] < in[p];
});
sve.erase(unique(sve.begin(),sve.end()), sve.end());
int where = 0;
function<void()>build = [&](){
int cp = sve[where];
where++;
int max_ind = in[cp] + sz[cp] - 1;
while(where < sve.size() && in[sve[where]] <= max_ind){
GC[cp].push_back({sve[where], dist[sve[where]] - dist[cp]});
GC[sve[where]].push_back({cp,dist[sve[where]] - dist[cp]});
build();
}
};
build();
//for (int i : sve)cout << " " << i;
// cout << endl;
for (int i = 0; i < T; i++){
crnci[Y[i]] = 1;
}
for (int i = 0; i < S; i++){
crnci[X[i]] = 2;
}
long long ans = Dijkstra(sve);
for (int i = 0; i < T; i++){
crnci[Y[i]] = 0;
}
for (int i = 0; i < S; i++){
crnci[X[i]] = 0;
}
for (int i = 0; i < (int)sve.size(); i++){
GC[sve[i]].clear();
dp[sve[i]] = (long long)1e18;
}
return ans;
}
} G;
void Init(int N, int A[], int B[], int D[]) {
G.dec(N);
for (int i = 0; i < N - 1; i++){
G.add_edge(++A[i],++B[i],D[i]);
}
G.init();
}
long long Query(int S, int X[], int T, int Y[]) {
return G.Query(S,X,T,Y);
}
Compilation message
factories.cpp: In lambda function:
factories.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | while(where < sve.size() && in[sve[where]] <= max_ind){
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
852 KB |
Output is correct |
| 2 |
Correct |
761 ms |
10756 KB |
Output is correct |
| 3 |
Correct |
783 ms |
10724 KB |
Output is correct |
| 4 |
Incorrect |
773 ms |
13412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
1878 ms |
158552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
852 KB |
Output is correct |
| 2 |
Correct |
761 ms |
10756 KB |
Output is correct |
| 3 |
Correct |
783 ms |
10724 KB |
Output is correct |
| 4 |
Incorrect |
773 ms |
13412 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
