Submission #310908

#	Time	Username	Problem	Language	Result	Execution time	Memory
310908		vipghn2003	Factories (JOI14_factories)	C++14	0 / 100	38 ms	24448 KiB

factories

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=5e5+5;
int n,m,p[N][21],level[N],sz[N],l[N],r[N],type[N],node[N*2];
long long mn[N][2],dep[N],res;
vector<pii>adj[N];
vector<int>g[N];

int cnt=0;
void dfs(int u)
{
    for(int i=1;i<=20;i++) p[u][i]=p[p[u][i-1]][i-1];
    cnt++;
    l[u]=cnt;
    for(auto&to:adj[u])
    {
        int v=to.fi;
        int w=to.se;
        if(v==p[u][0]) continue;
        p[v][0]=u;
        dep[v]=dep[u]+w;
        level[v]=level[u]+1;
        dfs(v);
    }
    r[u]=cnt;
}

int lca(int x,int y)
{
    if(level[x]>level[y]) swap(x,y);
    int diff=level[y]-level[x];
    for(int k=18;k>=0;k--) if(diff>>k&1) y=p[y][k];
    if (x==y) return x;
    for(int k=18;k>=0;k--)
    {
        if (p[x][k]!=p[y][k])
        {
            x=p[x][k];
            y=p[y][k];
        }
    }
    return p[x][0];
}

int dist(int u,int v)
{
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}

bool isParent(int p,int u)
{
    return (l[p]<=l[u]&&l[u]<=r[p]);
}

bool lf(const int &x,const int &y)
{
    return l[x]<l[y];
}

void Init(int N,int A[],int B[],int D[])
{
    n=N;
    for(int i=1;i<=n;i++) type[i]=-1;
    for(int i=0;i<n-1;i++)
    {
        int u=A[i];
        int v=B[i];
        int w=D[i];
        u++,v++;
        adj[u].push_back(mp(v,w));
        adj[v].push_back(mp(u,w));
    }
    dfs(1);
}

void go(int u,int par=-1)
{
    if(type[u]==0) mn[u][0]=dep[u];
    if(type[u]==1) mn[u][1]=dep[u];
    for(auto&v:g[u])
    {
        if(v==par) continue;
        go(v,u);
        res=min(res,mn[u][0]+mn[v][1]-2*dep[u]);
        res=min(res,mn[v][0]+mn[u][1]-2*dep[u]);
        mn[u][0]=min(mn[u][0],mn[v][0]);
        mn[u][1]=min(mn[u][1],mn[v][1]);
    }
}

long long Query(int S,int X[],int T,int Y[])
{
    int total_num=0;
    for(int i=0;i<S;i++)
    {
        X[i]++;
        type[X[i]]=0;
        total_num++;
        node[total_num]=X[i];
    }
    for(int i=0;i<T;i++)
    {
        Y[i]++;
        type[Y[i]]=1;
        total_num++;
        node[total_num]=Y[i];
    }
    sort(node+1,node+total_num+1,lf);
    total_num=unique(node+1,node+total_num+1)-node-1;
    int now=total_num;
    for(int i=1;i<now;i++)
    {
        total_num++;
        node[total_num]=lca(node[i],node[i+1]);
    }
    sort(node+1,node+total_num+1,lf);
    total_num=unique(node+1,node+total_num+1)-node-1;
    for(int i=1;i<=total_num;i++)
    {
        g[node[i]].clear();
        mn[node[i]][0]=1e18;
        mn[node[i]][1]=1e18;
    }
    stack<int>st;
    st.push(node[1]);
    for(int i=2;i<=total_num;i++)
    {
        while(!st.empty()&&!isParent(st.top(),node[i])) st.pop();
        if(!st.empty())
        {
            int par=st.top();
            g[par].push_back(node[i]);
            g[node[i]].push_back(par);
        }
        st.push(node[i]);
    }
    res=1e18;
    go(node[1]);
    return res;
}

/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    int a[n-1],b[n-1],d[n-1];
    for(int i=0;i<n-1;i++) cin>>a[i]>>b[i]>>d[i];
    Init(n,a,b,d);
    while(q--)
    {
        int s,t;
        cin>>s>>t;
        int x[s],y[t];
        for(int i=0;i<s;i++) cin>>x[i];
        for(int i=0;i<t;i++) cin>>y[i];
        cout<<Query(s,x,t,y)<<'\n';
    }
}
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
*/

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