Submission #362100

#	Time	Username	Problem	Language	Result	Execution time	Memory
362100		denkendoemeer	Factories (JOI14_factories)	C++14	100 / 100	6634 ms	344312 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool maxi(ll &a,ll b)
{
    if (a<b)
        return a=b,1;
    return 0;
}
bool mini(ll &a,ll b)
{
    if (a>b)
        return a=b,1;
    return 0;
}
struct ed
{
    int to,w;
};
vector<ed>e[500005];
struct grup
{
    int c;
    ll d;
};
vector<grup>g[500005];
int sum[500005],ok[500005];
ll ans,b1[500005],b2[500005];
int dfs(int nod,int t=-1)
{
    sum[nod]=1;
    for(auto it:e[nod])
        if (ok[it.to]==0 && it.to!=t)
            sum[nod]+=dfs(it.to,nod);
    return sum[nod];
}
int centr(int nod,int aux,int t=-1)
{
    for(auto it:e[nod])
        if (ok[it.to]==0 && it.to!=t)
            if (sum[it.to]*2>=aux)
                return centr(it.to,aux,nod);
    return nod;
}
int auxi;
void dfs2(int nod,int t=-1,ll dist=0)
{
    g[nod].push_back({auxi,dist});
    for(auto it:e[nod])
        if (ok[it.to]==0 && it.to!=t)
            dfs2(it.to,nod,dist+it.w);
}
void calc(int nod)
{
    int c=centr(nod,dfs(nod));
    auxi=c;
    dfs2(c);
    ok[c]=1;
    for(auto it:e[c])
        if (ok[it.to]==0)
            calc(it.to);
}
void Init(int n,int a[],int b[],int d[])
{
    int i;
    for(i=0;i<n-1;i++)
        e[a[i]].push_back({b[i],d[i]}),e[b[i]].push_back({a[i],d[i]});
    calc(0);
    memset(b1,0x3f,sizeof(b1));
    memset(b2,0x3f,sizeof(b2));
}
ll Query(int s,int x[],int t,int y[])
{
    ans=2e17;
    int i;
    for(i=0;i<s;i++)
        for(auto it:g[x[i]])
            mini(b2[it.c],it.d);
    for(i=0;i<t;i++)
        for(auto it:g[y[i]]){
            mini(b1[it.c],it.d);
            mini(ans,b1[it.c]+b2[it.c]);
        }
    for(i=0;i<s;i++)
        for(auto it:g[x[i]])
            b1[it.c]=b2[it.c]=2e17;
    for(i=0;i<t;i++)
        for(auto it:g[y[i]])
            b1[it.c]=b2[it.c]=2e17;
    return ans;
}

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