oj.uz

Submission #13564

# Submission time Handle Problem Language Result Execution time Memory
13564 2015-02-24T10:34:25 Z dohyun0324 Factories (JOI14_factories) C++
100 / 100
 4807 ms 211152 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 97708 KB Output is correct
2 Correct 1165 ms 98632 KB Output is correct
3 Correct 1241 ms 98500 KB Output is correct
4 Correct 1312 ms 98500 KB Output is correct
5 Correct 926 ms 98780 KB Output is correct
6 Correct 627 ms 98764 KB Output is correct
7 Correct 1203 ms 98500 KB Output is correct
8 Correct 1158 ms 98504 KB Output is correct
9 Correct 1000 ms 98780 KB Output is correct
10 Correct 500 ms 98764 KB Output is correct
11 Correct 1194 ms 98500 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 97708 KB Output is correct
2 Correct 2924 ms 194068 KB Output is correct
3 Correct 2408 ms 190352 KB Output is correct
4 Correct 1529 ms 211152 KB Output is correct
5 Correct 2067 ms 202116 KB Output is correct
6 Correct 2666 ms 190304 KB Output is correct
7 Correct 2207 ms 116316 KB Output is correct
8 Correct 1115 ms 120564 KB Output is correct
9 Correct 1757 ms 116652 KB Output is correct
10 Correct 2195 ms 116388 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 4799 ms 194068 KB Output is correct
2 Correct 4807 ms 194068 KB Output is correct
3 Correct 4523 ms 190396 KB Output is correct
4 Correct 4260 ms 190320 KB Output is correct
5 Correct 3969 ms 190692 KB Output is correct
6 Correct 3315 ms 204524 KB Output is correct
7 Correct 2208 ms 211152 KB Output is correct
8 Correct 4122 ms 190412 KB Output is correct
9 Correct 4225 ms 190796 KB Output is correct
10 Correct 4088 ms 190368 KB Output is correct
11 Correct 1741 ms 117136 KB Output is correct
12 Correct 1173 ms 120564 KB Output is correct
13 Correct 2424 ms 116980 KB Output is correct
14 Correct 2302 ms 116980 KB Output is correct
15 Correct 2262 ms 116404 KB Output is correct
16 Correct 2221 ms 116388 KB Output is correct