Submission #13564

#	Time	Username	Problem	Language	Result	Execution time	Memory
13564		dohyun0324	Factories (JOI14_factories)	C++98	100 / 100	4807 ms	211152 KiB

factories

#include "factories.h"
#include<vector>
#include<algorithm>
#include<string.h>
#define M 21474836470000000LL
using namespace std;
typedef pair<int,int> ppair;
ppair lev[500010];
int r,s,cnt,ch[500010],n,q,go[500010],num[500010],x,y,z,top[500010];
long long len[500010],dap;
vector<int>con[500010];
vector<int>cost[500010];
vector<long long>treeb[500010];
vector<long long>trees[500010];
struct data{
    int p,q;
    long long len;
}ch2[500010];
struct data2{
    int x,cost;
}anc[500010];
void dfs(int x,int l)
{
    int i;
    ch[x]=1; lev[x].first=l; lev[x].second=x;
    for(i=0;i<con[x].size();i++){
        if(ch[con[x][i]]) continue;
        anc[con[x][i]].x=x; anc[con[x][i]].cost=cost[x][i];
        dfs(con[x][i],l+1);
        num[x]+=num[con[x][i]];
    }
    num[x]++;
}
void dfs2(int x)
{
    int i,maxi=-2147483647,p=-1;
    ch2[x].p=cnt;
    top[cnt]++; ch2[x].q=top[cnt]; go[x]=s;
    for(i=0;i<con[x].size();i++){
        if(ch2[con[x][i]].p==0 && maxi<num[con[x][i]]) maxi=num[con[x][i]], p=i;
    }
    if(p==-1) return;
    ch2[con[x][p]].len=ch2[x].len+cost[x][p]; len[cnt]=ch2[x].len+cost[x][p];
    dfs2(con[x][p]);
}
void Init(int n, int A[], int B[], int D[])
{
    int i,j,t,c;
    for(i=0;i<n-1;i++){
        x=A[i]+1; y=B[i]+1; z=D[i];
        con[x].push_back(y); con[y].push_back(x);
        cost[x].push_back(z); cost[y].push_back(z);
    }
    dfs(1,1);
    sort(lev+1,lev+n+1);
    for(i=1;i<=n;i++){
        t=lev[i].second;
        if(!ch2[t].p){cnt++; s=t; dfs2(t);}
    }
    for(i=1;i<=cnt;i++){
        for(c=1;c<=top[i];c*=2);
        top[i]=c;
    }
    for(i=1;i<=cnt;i++){
        for(j=0;j<=top[i]*2;j++){treeb[i].push_back(M); trees[i].push_back(M);}
    }
}
void updateb(int p,int x,long long val,int sw)
{
    x+=top[p]-1; treeb[p][x]=min(treeb[p][x],val);
    if(sw==1) treeb[p][x]=M;
    x/=2;
    while(x){
        treeb[p][x]=min(treeb[p][x*2],treeb[p][x*2+1]);
        x/=2;
    }
}
void updates(int p,int x,long long val,int sw)
{
    x+=top[p]-1; trees[p][x]=min(trees[p][x],val);
    if(sw==1) trees[p][x]=M;
    x/=2;
    while(x){
        trees[p][x]=min(trees[p][x*2],trees[p][x*2+1]);
        x/=2;
    }
}
void pro1(int x,int sw)
{
    int p,q;
    long long sum=0;
    while(x){
        p=ch2[x].p; q=ch2[x].q;
        if(sw==0){
            updateb(p,q,sum+len[p]-ch2[x].len,0);
            updates(p,q,sum-len[p]+ch2[x].len,0);
        }
        else{
            updateb(p,q,M,1);
            updates(p,q,M,1);
        }
        sum+=ch2[x].len+anc[go[x]].cost;
        x=anc[go[x]].x;
    }
}
long long queryb(int p,int x,int y,int k,int s,int e)
{
    if(x>e || y<s) return M;
    if(s<=x && y<=e) return treeb[p][k];
    return min(queryb(p,x,(x+y)/2,k*2,s,e),queryb(p,(x+y)/2+1,y,k*2+1,s,e));
}
long long querys(int p,int x,int y,int k,int s,int e)
{
    if(x>e || y<s) return M;
    if(s<=x && y<=e) return trees[p][k];
    return min(querys(p,x,(x+y)/2,k*2,s,e),querys(p,(x+y)/2+1,y,k*2+1,s,e));
}
void pro2(int x)
{
    int p,q;
    long long sum=0;
    while(x){
        p=ch2[x].p; q=ch2[x].q;
        dap=min(dap,sum-len[p]+ch2[x].len+queryb(p,1,top[p],1,1,q));
        dap=min(dap,sum+len[p]-ch2[x].len+querys(p,1,top[p],1,q,top[p]));
        sum+=ch2[x].len+anc[go[x]].cost;
        x=anc[go[x]].x;
    }
}
long long Query(int S, int X[], int T, int Y[])
{
    int i,j;
    dap=M;
    for(i=0;i<S;i++) pro1(X[i]+1,0);
    for(i=0;i<T;i++) pro2(Y[i]+1);
    for(i=0;i<S;i++) pro1(X[i]+1,1);
    return dap;
}

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