#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
const ll inf = 10000000000000000;
#define fro front
vi euler_list;
vi euler_depth;
vector<pair<ii, ll>> tintout(500005, pair<ii, ll>(ii(-1, -1), 0));
vector<vector<ii>> x(500005);
ll vis[500005];
ll hi[500005];
struct segtree{
ll dd, ht, mid;
ll val;
segtree *L, *R;
segtree(ll l,ll r){
dd = l, ht =r; mid = (dd+ht)/2;
if(l == r){
val = inf;
}else{
L = new segtree(dd, mid); R = new segtree(mid+1, ht);
val = min(L -> val, R -> val);
}
}
void update(ll pos, ll newval){
if(dd == ht){
val = newval;
}else{
if(pos <= mid){
L -> update(pos, newval);
}else{
R -> update(pos, newval);
}
val = min(L -> val, R -> val);
}
}
ll query(ll l, ll r){
if(l == dd && r == ht) return val;
if(r <= mid){
return L -> query(l, r);
}else if(l > mid){
return R -> query(l, r);
}
return min(L -> query(l, mid), R -> query(mid+1, r));
}
};
segtree tree(0, 2000005);
void euler(ll no,ll h){
if(vis[no] != -1){
return;
}
vis[no] = 1;
hi[no] = h;
euler_list.pb(no);
euler_depth.pb(h);
for(auto e:x[no]){
euler(e.fi, h + e.se);
euler_depth.pb(h);
euler_list.pb(no);
}
return ;
}
void Init(int N, int A[], int B[], int D[]) {
for(ll i = 0; i < N; ++i){
x[A[i]].pb(ii(B[i], D[i]));
x[B[i]].pb(ii(A[i], D[i]));
}
for(ll i = 0; i < 500005; ++i){
tintout[i].second = i;
}
memset(vis, -1, sizeof vis);
euler(0, 0);
for(ll i = 0; i < euler_list.size(); ++i){
if(tintout[euler_list[i]].fi.fi == -1)
tintout[euler_list[i]].fi.fi = i;
tintout[euler_list[i]].fi.se = i;
}
for(int i = 0; i < euler_depth.size(); ++i){
tree.update(i, euler_depth[i]);
}
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = inf;
if(S <= 10 && T <= 10){
for(ll i = 0; i < S; ++i){
for(ll j = 0; j < T; ++j){
int a = tintout[X[i]].fi.fi;
int b = tintout[Y[j]].fi.fi;
ll l = min(a, b);
a = tintout[X[i]].fi.se;
b = tintout[Y[j]].fi.se;
ll r = max(a, b);
ll LCA = tree.query(l, r);
if(LCA == tintout[X[i]].fi.fi || LCA == tintout[Y[i]].fi.fi){
ans = min(ans, abs(hi[X[i]] - hi[Y[j]])) ;
}
ans = min(ans, hi[X[i]] - LCA + hi[Y[j]] - LCA);
}
}
}else{
priority_queue<ii, vector<ii>, greater<ii>> q;
ll dist[500005];
for(int i = 0; i < 500005; ++i){
dist[i] = inf;
}
for(ll i = 0; i < S; ++i){
q.push(ii(0, X[i]));
dist[X[i]] = 0;
}
while(!q.empty()){
ll price = q.top().fi;
ll node = q.top().se;
q.pop();
if(price != dist[node]){
continue;
}
for(auto e:x[node]){
if(dist[e.fi] > dist[node] + e.se){
q.push(ii(price + e.se, e.fi));
dist[e.fi] = price + e.se;
}
}
}
for(int i = 0; i < T; ++i){
ans = min(ans, dist[Y[i]]);
}
}
return ans;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:95:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(ll i = 0; i < euler_list.size(); ++i){
| ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = 0; i < euler_depth.size(); ++i){
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
282436 KB |
Output is correct |
| 2 |
Correct |
1297 ms |
293000 KB |
Output is correct |
| 3 |
Correct |
3539 ms |
300904 KB |
Output is correct |
| 4 |
Correct |
2389 ms |
301060 KB |
Output is correct |
| 5 |
Correct |
1215 ms |
300884 KB |
Output is correct |
| 6 |
Correct |
1232 ms |
300880 KB |
Output is correct |
| 7 |
Correct |
3440 ms |
300984 KB |
Output is correct |
| 8 |
Correct |
2839 ms |
300872 KB |
Output is correct |
| 9 |
Correct |
1219 ms |
300888 KB |
Output is correct |
| 10 |
Correct |
1162 ms |
300996 KB |
Output is correct |
| 11 |
Correct |
3417 ms |
300964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
282728 KB |
Output is correct |
| 2 |
Correct |
3273 ms |
348184 KB |
Output is correct |
| 3 |
Correct |
3066 ms |
347684 KB |
Output is correct |
| 4 |
Correct |
3285 ms |
359328 KB |
Output is correct |
| 5 |
Correct |
3470 ms |
365156 KB |
Output is correct |
| 6 |
Correct |
3282 ms |
349472 KB |
Output is correct |
| 7 |
Execution timed out |
8060 ms |
303144 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
282436 KB |
Output is correct |
| 2 |
Correct |
1297 ms |
293000 KB |
Output is correct |
| 3 |
Correct |
3539 ms |
300904 KB |
Output is correct |
| 4 |
Correct |
2389 ms |
301060 KB |
Output is correct |
| 5 |
Correct |
1215 ms |
300884 KB |
Output is correct |
| 6 |
Correct |
1232 ms |
300880 KB |
Output is correct |
| 7 |
Correct |
3440 ms |
300984 KB |
Output is correct |
| 8 |
Correct |
2839 ms |
300872 KB |
Output is correct |
| 9 |
Correct |
1219 ms |
300888 KB |
Output is correct |
| 10 |
Correct |
1162 ms |
300996 KB |
Output is correct |
| 11 |
Correct |
3417 ms |
300964 KB |
Output is correct |
| 12 |
Correct |
160 ms |
282728 KB |
Output is correct |
| 13 |
Correct |
3273 ms |
348184 KB |
Output is correct |
| 14 |
Correct |
3066 ms |
347684 KB |
Output is correct |
| 15 |
Correct |
3285 ms |
359328 KB |
Output is correct |
| 16 |
Correct |
3470 ms |
365156 KB |
Output is correct |
| 17 |
Correct |
3282 ms |
349472 KB |
Output is correct |
| 18 |
Execution timed out |
8060 ms |
303144 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
