oj.uz

Submission #238930

# Submission time Handle Problem Language Result Execution time Memory
238930 2020-06-13T14:20:56 Z MvC Factories (JOI14_factories) C++11
100 / 100
 4387 ms 216316 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12544 KB Output is correct
2 Correct 384 ms 21752 KB Output is correct
3 Correct 417 ms 21752 KB Output is correct
4 Correct 415 ms 21808 KB Output is correct
5 Correct 427 ms 21880 KB Output is correct
6 Correct 314 ms 21880 KB Output is correct
7 Correct 420 ms 21756 KB Output is correct
8 Correct 415 ms 21880 KB Output is correct
9 Correct 422 ms 21880 KB Output is correct
10 Correct 324 ms 21880 KB Output is correct
11 Correct 416 ms 21728 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12416 KB Output is correct
2 Correct 2177 ms 178680 KB Output is correct
3 Correct 3315 ms 178936 KB Output is correct
4 Correct 840 ms 179424 KB Output is correct
5 Correct 3786 ms 190712 KB Output is correct
6 Correct 3468 ms 180352 KB Output is correct
7 Correct 1010 ms 53624 KB Output is correct
8 Correct 496 ms 54560 KB Output is correct
9 Correct 1102 ms 56184 KB Output is correct
10 Correct 1047 ms 54840 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12544 KB Output is correct
2 Correct 384 ms 21752 KB Output is correct
3 Correct 417 ms 21752 KB Output is correct
4 Correct 415 ms 21808 KB Output is correct
5 Correct 427 ms 21880 KB Output is correct
6 Correct 314 ms 21880 KB Output is correct
7 Correct 420 ms 21756 KB Output is correct
8 Correct 415 ms 21880 KB Output is correct
9 Correct 422 ms 21880 KB Output is correct
10 Correct 324 ms 21880 KB Output is correct
11 Correct 416 ms 21728 KB Output is correct
12 Correct 18 ms 12416 KB Output is correct
13 Correct 2177 ms 178680 KB Output is correct
14 Correct 3315 ms 178936 KB Output is correct
15 Correct 840 ms 179424 KB Output is correct
16 Correct 3786 ms 190712 KB Output is correct
17 Correct 3468 ms 180352 KB Output is correct
18 Correct 1010 ms 53624 KB Output is correct
19 Correct 496 ms 54560 KB Output is correct
20 Correct 1102 ms 56184 KB Output is correct
21 Correct 1047 ms 54840 KB Output is correct
22 Correct 2455 ms 180392 KB Output is correct
23 Correct 2583 ms 182808 KB Output is correct
24 Correct 4100 ms 180972 KB Output is correct
25 Correct 3873 ms 208688 KB Output is correct
26 Correct 3940 ms 205048 KB Output is correct
27 Correct 4387 ms 216316 KB Output is correct
28 Correct 1034 ms 208096 KB Output is correct
29 Correct 3977 ms 205276 KB Output is correct
30 Correct 3952 ms 204676 KB Output is correct
31 Correct 4033 ms 205044 KB Output is correct
32 Correct 1104 ms 70520 KB Output is correct
33 Correct 512 ms 68928 KB Output is correct
34 Correct 795 ms 65608 KB Output is correct
35 Correct 810 ms 65580 KB Output is correct
36 Correct 1006 ms 65812 KB Output is correct
37 Correct 1028 ms 66012 KB Output is correct