#include<bits/stdc++.h>
#include<fstream>
#include "factories.h"
using namespace std;
ifstream fin("INTERNET.INP");
ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
const int mxn = 5e5, sq = 300, mxv = 1e4;
int n;
vt<pll>adj[mxn + 1];
int id[mxn + 1];
ll sz[mxn + 1], par[mxn + 1], ans[mxn + 1], tt = 0, l[mxn + 1];
vt<int>s, t;
ll dis[21][mxn + 1];
// map will TLE need to use this
bool vis[mxn + 1];
int dfs(int s, int pre){
sz[s] = 1;
for(auto [i, w]: adj[s]){
if(i != pre && !vis[i]){
sz[s] += dfs(i, s);
}
}
return(sz[s]);
}
int centroid(int s, int pre, int need){
for(auto [i, w]: adj[s]){
if(i != pre && !vis[i]){
if(sz[i] * 2 > need)return(centroid(i, s, need));
}
}
return(s);
}
void dfs2(int s, int step, int pre, ll d){
dis[step][s] = d;
for(auto [i, w]: adj[s]){
if(i != pre && !vis[i]){
dfs2(i, step, s, d + w);
}
}
}
void build(int s, int pre, int step){
int c = centroid(s, -1, dfs(s, -1));
vis[c] = true; par[c] = pre; id[c] = tt++;
dis[step][c] = 0; l[c] = step;
for(auto [i, w]: adj[c]){
if(i != pre && !vis[i]){
dfs2(i, step, c, w);
}
}
for(auto [i, w]: adj[c]){
if(!vis[i]){
build(i, c, step + 1);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++){
adj[A[i]].pb({B[i], D[i]}); adj[B[i]].pb({A[i], D[i]});
}
build(0, -1, 0); //centroid decompsoing the tree
for(int i = 0; i < n; i++)ans[i] = 1e18;
}
void add(int x){
int le = l[x];
for(int i = x; i != -1; i = par[i]){
ans[i] = min(ans[i], dis[le][i]); le--;
}
}
void rem(int x){
for(int i = x; i != -1; i = par[i])ans[i] = 1e18;
}
ll see(int x){
ll res = 1e18; int le = l[x];
for(int i = x; i != -1; i = par[i]){
res = min(res, ans[i] + dis[le][i]); le--;
}
return(res);
}
ll solve(){
for(int i = 0; i < s.size(); i++)add(s[i]);
ll res = 1e18;
for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
for(int i = 0; i < s.size(); i++)rem(s[i]);
return(res);
}
long long Query(int S, int X[], int T, int Y[]) {
s.clear(); t.clear();
for(int i = 0; i < S; i++)s.pb(X[i]);
for(int i = 0; i < T; i++)t.pb(Y[i]);
return(solve());
}
Compilation message
factories.cpp: In function 'int dfs(int, int)':
factories.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | for(auto [i, w]: adj[s]){
| ^
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
40 | for(auto [i, w]: adj[s]){
| ^
factories.cpp: In function 'void dfs2(int, int, int, long long int)':
factories.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
49 | for(auto [i, w]: adj[s]){
| ^
factories.cpp: In function 'void build(int, int, int)':
factories.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
59 | for(auto [i, w]: adj[c]){
| ^
factories.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
64 | for(auto [i, w]: adj[c]){
| ^
factories.cpp: In function 'long long int solve()':
factories.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i = 0; i < s.size(); i++)add(s[i]);
| ~~^~~~~~~~~~
factories.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
| ~~^~~~~~~~~~
factories.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i = 0; i < s.size(); i++)rem(s[i]);
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
