Submission #222899

#	Time	Username	Problem	Language	Result	Execution time	Memory
222899		mhy908	Factories (JOI14_factories)	C++14	15 / 100	8069 ms	380576 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=1987654321987654321;
int n, q, siz[500010], d[500010], sparse[500010][30], centpar[500010];
vector<pil> link[500010];
bool ch[500010];
LL dep[500010];
void dfs(int num, int par){
    siz[num]=1;
    d[num]=d[par]+1;
    sparse[num][0]=par;
    for(auto i:link[num]){
        if(i.F==par)continue;
        dep[i.F]=dep[num]+i.S;
        dfs(i.F, num);
        siz[num]+=siz[i.F];
    }
}
int lca(int x, int y){
    if(d[x]>d[y])swap(x, y);
    for(int i=20; i>=0; i--){
        if(d[y]-d[x]>=(1<<i))y=sparse[y][i];
    }
    if(x==y)return x;
    for(int i=20; i>=0; i--){
        if(sparse[x][i]!=sparse[y][i]){
            x=sparse[x][i];
            y=sparse[y][i];
        }
    }
    return sparse[x][0];
}
inline LL dist(int x, int y){return dep[x]+dep[y]-2*dep[lca(x, y)];}
int get_centroid(int num, int par, int sz){
    bool flag=true;
    for(auto i:link[num]){
        if(ch[i.F])continue;
        if(siz[i.F]>sz/2)flag=false;
    }
    if(flag)return num;
    for(auto i:link[num]){
        if(i.F==par||ch[i.F])continue;
        int temp=siz[i.F];
        siz[num]=sz-siz[i.F];
        siz[i.F]=sz;
        int ret=get_centroid(i.F, num, sz);
        if(ret)return ret;
        siz[num]=sz;
        siz[i.F]=temp;
    }
    return 0;
}
void make_centroidtree(int num, int par){
    int cen=get_centroid(num, 0, siz[num]);
    ch[cen]=true;
    centpar[cen]=par;
    for(auto i:link[cen]){
        if(ch[i.F])continue;
        make_centroidtree(i.F, cen);
    }
}
LL arr[500010];
vector<int> up[500010];
vector<LL> pardis[500010];
inline void update(int num){
    for(int i=0; i<up[num].size(); i++)arr[up[num][i]]=min(arr[up[num][i]], pardis[num][i]);
}
inline LL query(int num){
    LL ret=llinf;
    for(int i=0; i<up[num].size(); i++)ret=min(ret, arr[up[num][i]]+pardis[num][i]);
    return ret;
}
void cl(int num){
    for(int i=0; i<up[num].size(); i++){
        if(arr[up[num][i]]==llinf)break;
        arr[up[num][i]]=llinf;
    }
}
void Init(int N, int A[], int B[], int D[]){
    n=N;
    for(int i=0; i<n-1; i++){
        int a=A[i];
        int b=B[i];
        LL c=(LL)D[i];
        link[a+1].pb(mp(b+1, c));
        link[b+1].pb(mp(a+1, c));
    }
    for(int i=1; i<=n; i++)arr[i]=llinf;
    dfs(1, 0);
    for(int j=1; j<=20; j++){
        for(int i=1; i<=n; i++){
            sparse[i][j]=sparse[sparse[i][j-1]][j-1];
        }
    }
    make_centroidtree(1, 0);
    for(int i=1; i<=n; i++){
        int now=i;
        while(now){
            up[i].pb(now);
            pardis[i].pb(dist(i, now));
            now=centpar[now];
        }
    }
}
LL Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<S; i++)update(X[i]+1);
    LL ret=llinf;
    for(int i=0; i<T; i++)ret=min(ret, query(Y[i]+1));
    for(int i=0; i<S; i++)cl(X[i]+1);
    return ret;
}

Compilation message (stderr)

factories.cpp: In function 'void update(int)':
factories.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<up[num].size(); i++)arr[up[num][i]]=min(arr[up[num][i]], pardis[num][i]);
                  ~^~~~~~~~~~~~~~~
factories.cpp: In function 'LL query(int)':
factories.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<up[num].size(); i++)ret=min(ret, arr[up[num][i]]+pardis[num][i]);
                  ~^~~~~~~~~~~~~~~
factories.cpp: In function 'void cl(int)':
factories.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<up[num].size(); i++){
                  ~^~~~~~~~~~~~~~~

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