Submission #398108

#	Time	Username	Problem	Language	Result	Execution time	Memory
398108		cpp219	Factories (JOI14_factories)	C++14	0 / 100	40 ms	16256 KiB

factories

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll inf = 1e16 + 7;
vector<LL> g[N];
ll n,chainHead[N],curChain[N],posIn[N],now = 1,cnt = 1,child[N],dep[N],par[N];
ll suf[2][N],ans;
void DFS(ll u,ll p){
    child[u] = 1; par[u] = p; //cout<<par[0]<<"x\n"; //exit(0);
    //cout<<u<<" x "<<p<<"\n";
    for (auto i : g[u]){
        ll v = i.fs;
        if (v != p) dep[v] = dep[u] + i.sc,DFS(v,u),child[u] += child[v];
    }
}

void DFS_hld(ll u,ll p){
    curChain[u] = now;
    if (chainHead[now] == -1) chainHead[now] = u;
    ll chosen = -1,mx = 0;
    for (auto i : g[u]){
        ll v = i.fs;
        if (v != p&&child[v] > mx) mx = child[v],chosen = v;
    }
    if (chosen >= 0) DFS_hld(chosen,u);
    for (auto i : g[u]){
        ll v = i.fs;
        if (v != p&&v != chosen) now++,DFS_hld(v,u);
    }
}

void Init(int sz,int A[],int B[],int D[]){
    memset(chainHead,-1,sizeof(chainHead));
    for (ll i = 0;i < sz - 1;i++){
        ll x = A[i],y = B[i],w = D[i];
        g[x].push_back({y,w}); g[y].push_back({x,w});
    }
    DFS(0,-1); DFS_hld(0,-1);
}

struct Node{
    ll path,Lnode,d,type;
};

vector<Node> v;
/// suffix min

void To_root(ll now,ll d,ll type){
    while(now >= 0){
        ll path = curChain[now],nxt = par[chainHead[path]];
        //cout<<now<<" "<<par[3]; exit(0);
        v.push_back({path,now,d,type}); now = nxt;
    }
    //exit(0);
}

bool lf1(Node a,Node b){
    return a.path < b.path;
}

bool lf2(Node a,Node b){
    return dep[a.Lnode] < dep[b.Lnode] || (dep[a.Lnode] == dep[b.Lnode] && a.type < b.type);
}

void calSuf(ll L,ll R){
    vector<Node> have;
    for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
    suf[0][have.size()] = suf[1][have.size()] = inf;
    for (ll i = have.size() - 1;i >= 0;i--){
        suf[0][i] = suf[0][i + 1]; suf[1][i] = suf[1][i + 1];
        ll cur = have[i].type;
        suf[cur][i] = min(suf[cur][i],have[i].d);
    }
    //cout<<suf[0][1]; exit(0);
    for (ll i = have.size() - 1;i >= 0;i--){
        ll cur = have[i].type;
        ans = min(ans,have[i].d + suf[1 - cur][i + 1] - 2*dep[have[i].Lnode]);
        //cout<<have[i].d <<" "<< suf[1 - cur][i + 1] <<" "<< 2*dep[have[i].Lnode]<<"x\n";
    }
    //exit(0);
}

ll Query(int S,int X[],int T,int Y[]){
    v.clear(); ans = inf;
    for (ll i = 0;i < S;i++) To_root(X[i],dep[X[i]],0);
    for (ll i = 0;i < T;i++) To_root(Y[i],dep[Y[i]],1);
    sort(v.begin(),v.end(),lf1); ll sz = v.size();
    //for (auto i : v) cout<<i.path<<" "<<i.Lnode<<" "<<i.d<<" "<<i.type<<"\n"; cout<<"\n";
    //exit(0);
    for (ll i = 0;i < sz;i){
        if (v[i].type){
            i++; continue;
        }
        ll j = i + 1;
        while(j < sz&&v[j].path == v[i].path) j++;
        calSuf(i,j - 1); i = j;
        //cout<<v[i].d<<" "<<suf[i + 1]<<" "<<dep[v[i].Lnode]<<"\n";
    }
    return ans;
}

Compilation message (stderr)

factories.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
factories.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
factories.cpp: In function 'void calSuf(long long int, long long int)':
factories.cpp:76:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   76 |     for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
      |     ^~~
factories.cpp:76:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   76 |     for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
      |                                                     ^~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:99:26: warning: for increment expression has no effect [-Wunused-value]
   99 |     for (ll i = 0;i < sz;i){
      |                          ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67