Submission #48793

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48793	2018-05-18T18:40:51 Z	Pajaraja	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define MAXN 500007
#define MAXL 20
using namespace std;
vector<int> g[MAXN];
vector<long long> c[MAXN];
int p[MAXN],n,sz,cn,in[MAXN],gl,arr[MAXN],d[MAXN];
long long be[MAXL][MAXN],op[MAXN];
map <pair<int,int>,long long> m;
bool vc[MAXN];
int dfssize(int s,int f)
{
	int x=1;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]]) x+=dfssize(g[s][i],s);
	return x;
}
int dfsc(int s,int f)
{
	int x=1;
	bool ce=true;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]]) 
	{
		int a=dfsc(g[s][i],s);
		if(a>sz/2) ce=false;
		x+=a;
	}
	if(sz-x>sz/2) ce=false;
	if(ce) cn=s;
	return x;
}
void dfs(int s,int f,long long dist,int po)
{
	if(d[s]<d[po]) return;
	be[s][d[po]-d[s]]=dist;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,dist+c[s][i],po);
}
void centrodecomp(int s,int f,int du)
{
	sz=dfssize(s,-1);
	dfsc(s,-1);
	p[cn]=f;
	vc[cn]=true;
	d[cn]=du;
	int tmp=cn;
	for(int i=0;i<g[tmp].size();i++) if(!vc[g[tmp][i]]) centrodecomp(g[tmp][i],tmp,du+1);
}
void Init(int N, int A[], int B[], int D[]) 
{
	n=N;
	int root;
	for(int i=0;i<n-1;i++) {g[A[i]].push_back(B[i]); g[B[i]].push_back(A[i]); c[A[i]].push_back(D[i]); c[B[i]].push_back(D[i]);}
	centrodecomp(0,-1,0);
	for(int i=0;i<n;i++) dfs(i,-1,0,i);
	fill(opt,opt+MAXN,1000000000000000000LL);
}
long long Query(int S, int X[], int T, int Y[]) 
{
	int s=S,t=T;
	long long sk=1000000000000000000LL;
	for(int i=0;i<s;i++)
	{
		int a=X[i],cnt=0;
		while(a!=-1) {opt[a]=min(opt[a],be[X[i]][cnt]); a=p[a]; cnt++;}
	}
	for(int i=0;i<t;i++)
	{
		int a=Y[i],cnt=0;
		while(a!=-1) {sk=min(sk,be[Y[i]][cnt]+opt[a]); a=p[a]; cnt++;}
	}
	for(int i=0;i<s;i++)
	{
		int a=X[i];
		while(a!=-1) {opt[a]=1000000000000000000LL; a=p[a];}
	}
	return sk;
}

Compilation message

factories.cpp: In function 'int dfssize(int, int)':
factories.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]]) x+=dfssize(g[s][i],s);
              ~^~~~~~~~~~~~
factories.cpp: In function 'int dfsc(int, int)':
factories.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f && !vc[g[s][i]]) 
              ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs(int, int, long long int, int)':
factories.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,dist+c[s][i],po);
              ~^~~~~~~~~~~~
factories.cpp: In function 'void centrodecomp(int, int, int)':
factories.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[tmp].size();i++) if(!vc[g[tmp][i]]) centrodecomp(g[tmp][i],tmp,du+1);
              ~^~~~~~~~~~~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:55:7: error: 'opt' was not declared in this scope
  fill(opt,opt+MAXN,1000000000000000000LL);
       ^~~
factories.cpp:55:7: note: suggested alternative: 'op'
  fill(opt,opt+MAXN,1000000000000000000LL);
       ^~~
       op
factories.cpp:51:6: warning: unused variable 'root' [-Wunused-variable]
  int root;
      ^~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:64:17: error: 'opt' was not declared in this scope
   while(a!=-1) {opt[a]=min(opt[a],be[X[i]][cnt]); a=p[a]; cnt++;}
                 ^~~
factories.cpp:64:17: note: suggested alternative: 'op'
   while(a!=-1) {opt[a]=min(opt[a],be[X[i]][cnt]); a=p[a]; cnt++;}
                 ^~~
                 op
factories.cpp:69:41: error: 'opt' was not declared in this scope
   while(a!=-1) {sk=min(sk,be[Y[i]][cnt]+opt[a]); a=p[a]; cnt++;}
                                         ^~~
factories.cpp:69:41: note: suggested alternative: 'op'
   while(a!=-1) {sk=min(sk,be[Y[i]][cnt]+opt[a]); a=p[a]; cnt++;}
                                         ^~~
                                         op
factories.cpp:74:17: error: 'opt' was not declared in this scope
   while(a!=-1) {opt[a]=1000000000000000000LL; a=p[a];}
                 ^~~
factories.cpp:74:17: note: suggested alternative: 'op'
   while(a!=-1) {opt[a]=1000000000000000000LL; a=p[a];}
                 ^~~
                 op