oj.uz

Submission #219747

# Submission time Handle Problem Language Result Execution time Memory
219747 2020-04-06T08:45:37 Z nafis_shifat Factories (JOI14_factories) C++14
100 / 100
 6142 ms 204024 KB 
#include "factories.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;


const int mxn=5e5+6;
const ll inf=1e18;
vector<int> tree[mxn];
vector<ll> cost[mxn];

int subsz[mxn]={};
int centroidMarked[mxn]={};
int cpar[mxn];
ll cdist[24][mxn];

int level[mxn];


int n;



ll ans[mxn];

ll finW;


void dfs1(int cur,int prev,ll cst)
{
 
	for(int i=0;i<tree[cur].size();i++)
	{
		int v=tree[cur][i];
		if(v==prev)continue;
		dfs1(v,cur,cost[cur][i]);
	}
}



void dfs(int cur,int prev)
{
	subsz[cur]=1;
	for(auto i:tree[cur])
	{
		if(i!=prev && !centroidMarked[i])
		{
			dfs(i,cur);
			subsz[cur]+=subsz[i];
		}
	}

}
int getcentroid(int cur,int prev,int sz)
{
	bool isC=true;
	int hc=-1;

	for(int i=0;i<tree[cur].size();i++)
	{
		int v=tree[cur][i];
		if(v!=prev && !centroidMarked[v] && subsz[v]>sz)
		{
			isC=false;
			hc=v;
			break;
		}
	}
	if(isC && subsz[cur]>=sz)
	{
	
		return cur;
	}
	return getcentroid(hc,cur,sz);
}


int getcentroid(int src)
{
	dfs(src,-1);
	int c=getcentroid(src,-1,subsz[src]/2);
	centroidMarked[c]=1;
	return c;
}



void calc_dist(int cur,int prev,int l,ll d)
{
	cdist[l][cur]=d;
	
	for(int i=0;i<tree[cur].size();i++)
	{
		int v=tree[cur][i];
		if(v==prev || centroidMarked[v])continue;

		calc_dist(v,cur,l,d+cost[cur][i]);
	}
}


int build(int root,int lv)
{
	int c=getcentroid(root);
	calc_dist(c,-1,lv,0);
	level[c]=lv;
	for(int i=0;i<tree[c].size();i++)
	{
		int v=tree[c][i];
		if(!centroidMarked[v])
		{
			int k=build(v,lv+1);
			cpar[k]=c;
		}
	}

	return c;
	
}


void Init(int N, int A[], int B[], int D[])
{
	n=N;
	for(int i=0;i<n-1;i++)
	{
	   
		tree[A[i]].push_back(B[i]);
		tree[B[i]].push_back(A[i]);

		cost[A[i]].push_back(D[i]);
		cost[B[i]].push_back(D[i]);
	}

	dfs1(0,-1,0);
	
	cpar[build(0,0)]=-1;
    for(int i=0;i<n;i++)ans[i]=inf;

}


void prc(int u,bool f)
{
	
	int lv=level[u]-1;
	ans[u]=(f?0:inf);
	int cur=cpar[u];

	while(cur!=-1)
	{
	   
		if(f)ans[cur]=min(ans[cur],cdist[lv][u]);
		else ans[cur]=inf;
	
		cur=cpar[cur];
		lv--;
		
	}
}

long long Query(int S, int X[], int T, int Y[])
{
	for(int i=0;i<S;i++)prc(X[i],true);

	ll res=inf;

    for(int i=0;i<T;i++)
    {
    	int lv=level[Y[i]]-1;
    	int cur=cpar[Y[i]];
    	res=min(res,ans[Y[i]]);
  
    	while(cur!=-1)
    	{
    	    
    		res=min(res,ans[cur]+cdist[lv][Y[i]]);
    	  
    		cur=cpar[cur];
    		lv--;

    	}
    }

    for(int i=0;i<S;i++)prc(X[i],false);



    return res;
}

Compilation message

factories.cpp: In function 'void dfs1(int, int, long long int)':
factories.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[cur].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'int getcentroid(int, int, int)':
factories.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[cur].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void calc_dist(int, int, int, long long int)':
factories.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[cur].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'int build(int, int)':
factories.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[c].size();i++)
              ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24312 KB Output is correct
2 Correct 407 ms 33016 KB Output is correct
3 Correct 429 ms 33016 KB Output is correct
4 Correct 434 ms 33016 KB Output is correct
5 Correct 450 ms 33272 KB Output is correct
6 Correct 332 ms 32504 KB Output is correct
7 Correct 431 ms 33016 KB Output is correct
8 Correct 442 ms 32972 KB Output is correct
9 Correct 457 ms 33272 KB Output is correct
10 Correct 334 ms 32504 KB Output is correct
11 Correct 452 ms 32888 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 2555 ms 142456 KB Output is correct
3 Correct 3887 ms 158696 KB Output is correct
4 Correct 980 ms 111692 KB Output is correct
5 Correct 5190 ms 200244 KB Output is correct
6 Correct 3993 ms 178704 KB Output is correct
7 Correct 1240 ms 71164 KB Output is correct
8 Correct 506 ms 60772 KB Output is correct
9 Correct 1478 ms 75736 KB Output is correct
10 Correct 1251 ms 72824 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24312 KB Output is correct
2 Correct 407 ms 33016 KB Output is correct
3 Correct 429 ms 33016 KB Output is correct
4 Correct 434 ms 33016 KB Output is correct
5 Correct 450 ms 33272 KB Output is correct
6 Correct 332 ms 32504 KB Output is correct
7 Correct 431 ms 33016 KB Output is correct
8 Correct 442 ms 32972 KB Output is correct
9 Correct 457 ms 33272 KB Output is correct
10 Correct 334 ms 32504 KB Output is correct
11 Correct 452 ms 32888 KB Output is correct
12 Correct 19 ms 24064 KB Output is correct
13 Correct 2555 ms 142456 KB Output is correct
14 Correct 3887 ms 158696 KB Output is correct
15 Correct 980 ms 111692 KB Output is correct
16 Correct 5190 ms 200244 KB Output is correct
17 Correct 3993 ms 178704 KB Output is correct
18 Correct 1240 ms 71164 KB Output is correct
19 Correct 506 ms 60772 KB Output is correct
20 Correct 1478 ms 75736 KB Output is correct
21 Correct 1251 ms 72824 KB Output is correct
22 Correct 3081 ms 167180 KB Output is correct
23 Correct 3168 ms 172124 KB Output is correct
24 Correct 4710 ms 184776 KB Output is correct
25 Correct 4761 ms 188552 KB Output is correct
26 Correct 4689 ms 184952 KB Output is correct
27 Correct 6142 ms 204024 KB Output is correct
28 Correct 1161 ms 122036 KB Output is correct
29 Correct 4678 ms 184568 KB Output is correct
30 Correct 4714 ms 184328 KB Output is correct
31 Correct 4691 ms 184628 KB Output is correct
32 Correct 1399 ms 76184 KB Output is correct
33 Correct 505 ms 61156 KB Output is correct
34 Correct 854 ms 66552 KB Output is correct
35 Correct 873 ms 66680 KB Output is correct
36 Correct 1119 ms 69624 KB Output is correct
37 Correct 1155 ms 69684 KB Output is correct