#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int U=5e5+5;
bool f[U];
ll d[U],Dist[U];
int P[U][21];
int timer,in[U],out[U];
vector < int > rec,ver;
vector < pair < int , ll > > g[U];
vector < pair < int , int > > v[U];
priority_queue < pair < ll , int > > pq;
bool is_anc(int a,int b) {
return (in[a]<=in[b] && out[b]<=out[a]);
}
int LCA(int a,int b) {
if (is_anc(a,b)) return a;
for (int i=19; i>=0; i--)
if (!is_anc(P[a][i],b)) a=P[a][i];
return P[a][0];
}
void Dfs(int x,int p,ll dist) {
in[x]=++timer;
d[x]=dist;
P[x][0]=p;
int to,cost;
for (int i=0; i<v[x].size(); i++) {
to=v[x][i].F;
cost=v[x][i].S;
if (to!=p) Dfs(to,x,dist+cost);
}
out[x]=timer;
}
void Init(int n, int a[], int b[], int c[]) {
assert(n<=100000);
for (int i=0; i<n; i++) {
v[a[i]].pb({b[i],c[i]});
v[b[i]].pb({a[i],c[i]});
}
Dfs(0,0,0);
for (int j=1; j<=19; j++)
for (int i=1; i<=n; i++)
P[i][j]=P[P[i][j-1]][j-1];
}
bool cmp(int a,int b) {
return in[a]<in[b];
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i=0; i<S; i++) {
ver.pb(X[i]);
}
for (int i=0; i<T; i++) {
ver.pb(Y[i]);
}
sort(ver.begin(),ver.end(),cmp);
ll dist;
int vert;
for (int i=0; i<S+T; i++) {
if (!i) continue;
vert=LCA(ver[i-1],ver[i]);
ver.pb(in[vert]);
}
sort(ver.begin(),ver.end(),cmp);
vert=ver[0];
for (int i=1; i<ver.size(); i++) {
if (ver[i]==ver[i-1]) continue;
if (ver[i]==vert) continue;
while (!(is_anc(vert,ver[i]))) {
vert=rec.back();
rec.pop_back();
}
dist=d[ver[i]]-d[vert];
g[vert].pb({ver[i],dist});
g[ver[i]].pb({vert,dist});
rec.pb(vert);
vert=ver[i];
}
while (rec.size())
rec.pop_back();
for (int i=0; i<ver.size(); i++) {
if (i && ver[i]==ver[i-1]) continue;
Dist[ver[i]]=1e15;
}
for (int i=0; i<S; i++) {
Dist[X[i]]=0;
}
for (int i=0; i<ver.size(); i++) {
if (i && ver[i]==ver[i-1]) continue;
pq.push({-Dist[ver[i]],ver[i]});
}
int to,x;
ll cost;
while (!pq.empty()) {
x=pq.top().S;
pq.pop();
if (f[x]) continue;
f[x]=true;
for (int i=0; i<g[x].size(); i++) {
to=g[x][i].F;
cost=g[x][i].S;
if (!f[to] && Dist[x]+cost<Dist[to]) {
Dist[to]=Dist[x]+cost;
pq.push({-Dist[to],to});
}
}
}
ll ans=1e15;
for (int i=0; i<T; i++) {
ans=min(ans,Dist[Y[i]]);
}
for (int i=0; i<ver.size(); i++) {
g[ver[i]].clear();
f[ver[i]]=false;
Dist[ver[i]]=0;
}
ver.clear();
return ans;
}
Compilation message
factories.cpp: In function 'void Dfs(int, int, long long int)':
factories.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i=0; i<v[x].size(); i++) {
| ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i=1; i<ver.size(); i++) {
| ~^~~~~~~~~~~
factories.cpp:105:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i=0; i<ver.size(); i++) {
| ~^~~~~~~~~~~
factories.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int i=0; i<ver.size(); i++) {
| ~^~~~~~~~~~~
factories.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int i=0; i<g[x].size(); i++) {
| ~^~~~~~~~~~~~
factories.cpp:141:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int i=0; i<ver.size(); i++) {
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
48748 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
48488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
48748 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
