Submission #238930

#	Time	Username	Problem	Language	Result	Execution time	Memory
238930		MvC	Factories (JOI14_factories)	C++11	100 / 100	4387 ms	216316 KiB

factories

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include "factories.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=5e5+50;
const ll mod=1e9+7;
using namespace std;
int n,sz[nmax],tin[nmax],tout[nmax],tt,up[nmax][20],cent[nmax],par[nmax],viz[nmax];
ll lvl[nmax],cur[nmax],ds[nmax][20];
vector<int>vc;
vector<pair<int,int> >a[nmax];
void dfs_sz(int u,int p)
{
	sz[u]=1;
	for(int i=0;i<(int)a[u].size();i++)
	{
		int v=a[u][i].fr;
		if(cent[v] || v==p)continue;
		dfs_sz(v,u);
		sz[u]+=sz[v];
	}
}
int dfs_cent(int u,int p,int siz)
{
	for(int i=0;i<(int)a[u].size();i++)
	{
		int v=a[u][i].fr;
		if(cent[v] || v==p)continue;
		if(sz[v]>siz/2)return dfs_cent(v,u,siz);
	}
	return u;
}
void decompose(int root,int p=-1)
{
	dfs_sz(root,p);
	int c=dfs_cent(root,p,sz[root]);
	par[c]=p;
	cent[c]=1;
	for(int i=0;i<(int)a[c].size();i++)
	{
		int v=a[c][i].fr;
		if(cent[v])continue;
		decompose(v,c);
	}
}
void dfs(int x,int p,int d)
{
    tin[x]=++tt;
    lvl[x]=lvl[p]+1LL*d;
    up[x][0]=p;
    for(int i=1;i<19;i++)up[x][i]=up[up[x][i-1]][i-1];
    for(int i=0;i<(int)a[x].size();i++)if(a[x][i].fr!=p)dfs(a[x][i].fr,x,a[x][i].sc);
    tout[x]=++tt;
}
int anc(int x,int y)
{
    return tin[x]<=tin[y] && tout[x]>=tout[y];
}
int lca(int x,int y)
{
    if(anc(x,y))return x;
    if(anc(y,x))return y;
    for(int i=18;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
    return up[x][0];
}
ll dist(int x,int y)
{
	return lvl[x]+lvl[y]-2LL*lvl[lca(x,y)];
}
void Init(int N,int A[],int B[],int D[])
{
	int l,i,x;
	n=N;
	for(i=0;i<n-1;i++)
	{
		A[i]++,B[i]++;
		a[A[i]].pb(mkp(B[i],D[i]));
		a[B[i]].pb(mkp(A[i],D[i]));
	}
	dfs(1,1,0);
	decompose(1);
	for(i=1;i<=n;i++)cur[i]=llinf;
	for(i=1;i<=n;i++)
	{
		x=i,l=0;
		while(x>=1)
		{
			ds[i][l]=dist(i,x);
			l++;
			x=par[x];
		}
	}
}
ll Query(int s,int X[],int t,int Y[])
{
	int i,x,l;
	ll rs=llinf;
	for(i=0;i<s;i++)
	{
		x=++X[i],l=0;
		while(x>=1)
		{
			cur[x]=min(cur[x],ds[X[i]][l]);
			l++;
			x=par[x];
		}
	}
	for(i=0;i<t;i++)
	{
		x=++Y[i],l=0;
		while(x>=1)
		{
			rs=min(rs,cur[x]+ds[Y[i]][l]);
			l++;
			x=par[x];
		}
	}
	for(i=0;i<s;i++)
	{
		x=X[i];
		while(x>=1)
		{
			cur[x]=llinf;
			x=par[x];
		}
	}
	return rs;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
	return 0;
}*/

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