oj.uz

Submission #76450

# Submission time Handle Problem Language Result Execution time Memory
76450 2018-09-13T14:15:17 Z nxteru Factories (JOI14_factories) C++14
100 / 100
 7920 ms 426136 KB 
#include "factories.h" 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int n,k,par[500005][19],dp[500005],pre[500005],pro[500005],vs[1000005],id[500005],seg[(1<<21)+1],qx[500005],qy[500005];
ll x[500005],y[500005],ans,dps[1000005];
vector<P>g[500005];
vector<P>G[500005];
vector<int>cm;
vector<int>z;
void dfs(int v,int p,int d,ll da){
    dps[k]=da;
    vs[k]=v;
    pre[v]=k++;
    par[v][0]=p;
    dp[v]=d;
    for(int i=0;i<g[v].size();i++){
        if(g[v][i].F!=p)dfs(g[v][i].F,v,d+1,da+g[v][i].S);
    }
    dps[k]=da;
    vs[k]=v;
    pro[v]=k++;
}
int rmin(int a,int b){
    if(dps[a]>dps[b])return b;
    return a;
}
void up(int a,int b){
    a++;
    a+=(1<<20);
    seg[a]=b;
    while(a/=2){
        seg[a]=rmin(seg[a*2],seg[a*2+1]);
    }
}
int que(int l,int r){
    l++;
    r++;
    int res=n*2;
    l+=(1<<20);
    r+=(1<<20);
    for (;l<r; l>>=1, r>>=1) {
        if(r&1){
            r--;
            res=rmin(res,seg[r]);
        }
        if(l&1){
            res=rmin(res,seg[l]);
            l++;
        }
    }
    return res;
}
int lca(int v,int u){
    if(dp[v]>dp[u])swap(v,u);
    if(par[u][18]!=-1&&dp[par[u][18]]>=dp[v])u=par[u][18];
    for(int i=0;i<19;i++){
        if((dp[u]-dp[v])>>i&1)u=par[u][i];
    }
    if(u==v)return v;
    for(int i=18;i>=0;i--){
        if(par[v][i]!=par[u][i]){
            v=par[v][i];
            u=par[u][i];
        }
    }
    return par[v][0];
}
void s_dfs(int v,int p,int lm,int rm){
    if(p!=-1){
        G[id[p]].PB(P(id[v],dps[pre[v]]-dps[pre[p]]));
        G[id[v]].PB(P(id[p],dps[pre[v]]-dps[pre[p]]));
    }
    if(pre[v]+1<=pro[v]-1){
        int w=que(pre[v]+1,pro[v]-1);
        if(w!=2*n)s_dfs(vs[w],v,pre[v],pro[v]);
    }
    if(lm+1<=pre[v]-1){
        int w=que(lm+1,pre[v]-1);
        if(w!=2*n)s_dfs(vs[w],p,lm,pre[v]);
    }
    if(pro[v]+1<=rm-1){
        int w=que(pro[v]+1,rm-1);
        if(w!=2*n)s_dfs(vs[w],p,pro[v],rm);
    }
}
void a_dfs(int v,int p){
    for(int i=0;i<G[v].size();i++){
        int u=G[v][i].F;
        ll c=G[v][i].S;
        if(u!=p){
            a_dfs(u,v);
            x[v]=min(x[v],x[u]+c);
            y[v]=min(y[v],y[u]+c);
        }
    }
    ans=min(ans,x[v]+y[v]);
}
void Init(int N,int *A,int *B,int *d){
    n=N;
    for(int i=0;i<n;i++)id[i]=-1;
    for(int i=0;i<=(1<<21);i++)seg[i]=n*2;
    for(int i=0;i<n-1;i++){
        g[A[i]].PB(P(B[i],d[i]));
        g[B[i]].PB(P(A[i],d[i]));
    }
    dfs(0,-1,0,0);
    dps[n*2]=INF;
    for(int i=0;i<18;i++){
        for(int v=0;v<n;v++){
            if(par[v][i]==-1)par[v][i+1]=-1;
            else par[v][i+1]=par[par[v][i]][i];
        }
    }
}
ll Query(int s,int *X,int t,int *Y){
    k=0;
    cm.clear();
    z.clear();
    for(int i=0;i<s;i++){
        if(id[X[i]]==-1){
            cm.PB(pre[X[i]]);
            up(pre[X[i]],pre[X[i]]);
            id[X[i]]=k++;
        }
    }
    for(int i=0;i<t;i++){
        if(id[Y[i]]==-1){
            cm.PB(pre[Y[i]]);
            up(pre[Y[i]],pre[Y[i]]);
            id[Y[i]]=k++;
        }
    }
    sort(cm.begin(),cm.end());
    for(int i=1;i<cm.size();i++){
        int a=lca(vs[cm[i]],vs[cm[i-1]]);
        if(id[a]==-1){
            id[a]=k++;
            up(pre[a],pre[a]);
        }
        z.PB(a);
    }
    int r=que(pre[0],pro[0]);
    s_dfs(vs[r],-1,pre[r],pro[r]);
    ans=INF;
    for(int i=0;i<k;i++){
        x[i]=INF;
        y[i]=INF;
    }
    for(int i=0;i<s;i++)x[id[X[i]]]=0;
    for(int i=0;i<t;i++)y[id[Y[i]]]=0;
    a_dfs(id[vs[r]],-1);
    for(int i=0;i<z.size();i++){
        up(pre[z[i]],n*2);
        id[z[i]]=-1;
    }
    for(int i=0;i<s;i++){
        up(pre[X[i]],n*2);
        id[X[i]]=-1;
    }
    for(int i=0;i<t;i++){
        up(pre[Y[i]],n*2);
        id[Y[i]]=-1;
    }
    for(int i=0;i<k;i++)G[i].clear();
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int, int, ll)':
factories.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++){
                 ~^~~~~~~~~~~~
factories.cpp: In function 'void a_dfs(int, int)':
factories.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[v].size();i++){
                 ~^~~~~~~~~~~~
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:144:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<cm.size();i++){
                 ~^~~~~~~~~~
factories.cpp:162:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<z.size();i++){
                 ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 32504 KB Output is correct
2 Correct 1702 ms 42080 KB Output is correct
3 Correct 2001 ms 42080 KB Output is correct
4 Correct 1884 ms 42080 KB Output is correct
5 Correct 1472 ms 42080 KB Output is correct
6 Correct 1542 ms 70844 KB Output is correct
7 Correct 2203 ms 70844 KB Output is correct
8 Correct 1866 ms 70844 KB Output is correct
9 Correct 1474 ms 70844 KB Output is correct
10 Correct 1495 ms 70844 KB Output is correct
11 Correct 2202 ms 70844 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70844 KB Output is correct
2 Correct 3426 ms 127596 KB Output is correct
3 Correct 4528 ms 131692 KB Output is correct
4 Correct 2585 ms 131692 KB Output is correct
5 Correct 4134 ms 162184 KB Output is correct
6 Correct 4860 ms 162184 KB Output is correct
7 Correct 5050 ms 162184 KB Output is correct
8 Correct 2836 ms 162184 KB Output is correct
9 Correct 4166 ms 162184 KB Output is correct
10 Correct 4974 ms 162184 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 32504 KB Output is correct
2 Correct 1702 ms 42080 KB Output is correct
3 Correct 2001 ms 42080 KB Output is correct
4 Correct 1884 ms 42080 KB Output is correct
5 Correct 1472 ms 42080 KB Output is correct
6 Correct 1542 ms 70844 KB Output is correct
7 Correct 2203 ms 70844 KB Output is correct
8 Correct 1866 ms 70844 KB Output is correct
9 Correct 1474 ms 70844 KB Output is correct
10 Correct 1495 ms 70844 KB Output is correct
11 Correct 2202 ms 70844 KB Output is correct
12 Correct 36 ms 70844 KB Output is correct
13 Correct 3426 ms 127596 KB Output is correct
14 Correct 4528 ms 131692 KB Output is correct
15 Correct 2585 ms 131692 KB Output is correct
16 Correct 4134 ms 162184 KB Output is correct
17 Correct 4860 ms 162184 KB Output is correct
18 Correct 5050 ms 162184 KB Output is correct
19 Correct 2836 ms 162184 KB Output is correct
20 Correct 4166 ms 162184 KB Output is correct
21 Correct 4974 ms 162184 KB Output is correct
22 Correct 6196 ms 214216 KB Output is correct
23 Correct 6045 ms 240232 KB Output is correct
24 Correct 6455 ms 262092 KB Output is correct
25 Correct 6715 ms 290520 KB Output is correct
26 Correct 7655 ms 298112 KB Output is correct
27 Correct 5866 ms 353484 KB Output is correct
28 Correct 4443 ms 376416 KB Output is correct
29 Correct 7920 ms 376416 KB Output is correct
30 Correct 7731 ms 393032 KB Output is correct
31 Correct 7827 ms 417872 KB Output is correct
32 Correct 2851 ms 417872 KB Output is correct
33 Correct 2479 ms 417872 KB Output is correct
34 Correct 3392 ms 417872 KB Output is correct
35 Correct 3306 ms 417872 KB Output is correct
36 Correct 3948 ms 417872 KB Output is correct
37 Correct 4034 ms 426136 KB Output is correct