#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,lg=20;
struct yal{
long long u,v,w;
int getad(int fu){
return (u^v^fu);
}
}alle[maxn];
long long mainres,n,lca[lg][maxn],inf=1e16,vis1[maxn],vis2[maxn],timea,high[maxn];
pair<long long,long long>stf[maxn];
vector<long long>adj[maxn],adjt[maxn];
vector<long long>all;
pair<long long,long long> dfsres(long long u){
cout<<"chymisge "<<u<<endl;
pair<long long,long long>ret=make_pair(inf,inf);
if(vis1[u]){
ret.first=high[u];
}
if(vis2[u]){
ret.second=high[u];
}
mainres=min(mainres,ret.first+ret.second-2*high[u]);
for(auto x:adjt[u]){
pair<long long,long long>fake=dfsres(x);
mainres=min(mainres,fake.first+ret.second-2*high[u]);
mainres=min(mainres,fake.second+ret.first-2*high[u]);
ret.first=min(fake.first,ret.first);
ret.second=min(fake.second,ret.second);
}
return ret;
}
bool zird(long long u,long long v){
return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}
void dfs(long long u,long long par=-1){
timea++;
stf[u].first=timea;
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(v==par){
continue;
}
lca[0][v]=u;
high[v]=high[u]+alle[x].w;
dfs(v,u);
}
stf[u].second=timea;
}
void callca(){
for(long long i=1;i<lg;i++){
for(long long j=1;j<=n;j++){
lca[i][j]=lca[i-1][lca[i-1][j]];
}
}
}
long long getlca(long long u,long long v){
if(zird(u,v)){
return v;
}
if(zird(v,u)){
return u;
}
for(long long i=lg-1;i>=0;i--){
if(lca[i][u]!=-1&&zird(v,lca[i][u])==0){
u=lca[i][u];
}
}
cout<<"nago: "<<u<<" "<<lca[0][u]<<" "<<zird(v,lca[0][u])<<endl;
return lca[0][u];
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(long long i=0;i<n;i++){
alle[i].u=A[i];
alle[i].v=B[i];
alle[i].w=D[i];
adj[alle[i].u].push_back(i);
adj[alle[i].v].push_back(i);
}
for(int i=0;i<lg;i++){
for(int j=0;j<maxn;j++){
lca[i][j]=-1;
}
}
dfs(0);
callca();
//assert(0);
}
bool cmp(long long a,long long b){
return stf[a].first<stf[b].first;
}
long long calres(long long a,int A[],long long b,int B[]){
for(long long i=0;i<a;i++){
vis1[A[i]]=1;
}
for(long long i=0;i<b;i++){
vis2[B[i]]=1;
}
mainres=inf;
dfsres(0);
for(auto x:all){
vis1[x]=vis2[x]=0;
adjt[x].clear();
}
all.clear();
return mainres;
}
void create(long long a,int A[],long long b,int B[]){
for(long long i=0;i<a;i++){
all.push_back(A[i]);
}
for(long long i=0;i<b;i++){
all.push_back(B[i]);
}
all.push_back(0);
sort(all.begin(),all.end(),cmp);
for(long long i=0;i<a+b;i++){
all.push_back(getlca(all[i],all[i+1]));
}
sort(all.begin(),all.end());
all.resize(unique(all.begin(),all.end())-all.begin());
sort(all.begin(),all.end(),cmp);
vector<long long>v={0};
if(all[0]!=0){
cout<<"wtf:\n";
for(auto x:all){
cout<<x<<" ";
}
cout<<"\n";
assert(0);
}
for(long long i=1;i<(long long)all.size();i++){
while(stf[v.back()].second<stf[all[i]].first){
v.pop_back();
}
adjt[v.back()].push_back(all[i]);
v.push_back(all[i]);
}
}
long long Query(int S, int X[], int T, int Y[]) {
// cout<<"wtf"<<endl;
create(S,X,T,Y);
// cout<<"ha"<<endl;
return calres(S,X,T,Y);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
125268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
121940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
125268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
