oj.uz

Submission #74254

# Submission time Handle Problem Language Result Execution time Memory
74254 2018-08-30T16:02:26 Z Pajaraja Factories (JOI14_factories) C++17
33 / 100
 8000 ms 388176 KB 
#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[MAXN][MAXL],opt[MAXN];
bool vc[MAXN];
inline 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;
}
inline 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;
}
inline void dfs(int s,int f,long long dist,int po)
{
	if(d[s]<d[po]) return;
	be[s][d[s]-d[po]]=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:14: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:21: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:35: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:45: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:50:6: warning: unused variable 'root' [-Wunused-variable]
  int root;
      ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28152 KB Output is correct
2 Correct 403 ms 37116 KB Output is correct
3 Correct 393 ms 37284 KB Output is correct
4 Correct 388 ms 37284 KB Output is correct
5 Correct 417 ms 46824 KB Output is correct
6 Correct 307 ms 56128 KB Output is correct
7 Correct 396 ms 65704 KB Output is correct
8 Correct 415 ms 75184 KB Output is correct
9 Correct 421 ms 84908 KB Output is correct
10 Correct 316 ms 94020 KB Output is correct
11 Correct 447 ms 103596 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 103596 KB Output is correct
2 Correct 3620 ms 224800 KB Output is correct
3 Correct 5680 ms 224800 KB Output is correct
4 Correct 1158 ms 226772 KB Output is correct
5 Correct 7805 ms 241448 KB Output is correct
6 Correct 5641 ms 241448 KB Output is correct
7 Correct 1140 ms 241448 KB Output is correct
8 Correct 550 ms 241448 KB Output is correct
9 Correct 1637 ms 241448 KB Output is correct
10 Correct 1278 ms 241448 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28152 KB Output is correct
2 Correct 403 ms 37116 KB Output is correct
3 Correct 393 ms 37284 KB Output is correct
4 Correct 388 ms 37284 KB Output is correct
5 Correct 417 ms 46824 KB Output is correct
6 Correct 307 ms 56128 KB Output is correct
7 Correct 396 ms 65704 KB Output is correct
8 Correct 415 ms 75184 KB Output is correct
9 Correct 421 ms 84908 KB Output is correct
10 Correct 316 ms 94020 KB Output is correct
11 Correct 447 ms 103596 KB Output is correct
12 Correct 28 ms 103596 KB Output is correct
13 Correct 3620 ms 224800 KB Output is correct
14 Correct 5680 ms 224800 KB Output is correct
15 Correct 1158 ms 226772 KB Output is correct
16 Correct 7805 ms 241448 KB Output is correct
17 Correct 5641 ms 241448 KB Output is correct
18 Correct 1140 ms 241448 KB Output is correct
19 Correct 550 ms 241448 KB Output is correct
20 Correct 1637 ms 241448 KB Output is correct
21 Correct 1278 ms 241448 KB Output is correct
22 Correct 3860 ms 250640 KB Output is correct
23 Correct 3826 ms 277500 KB Output is correct
24 Correct 6212 ms 300088 KB Output is correct
25 Correct 6378 ms 328144 KB Output is correct
26 Correct 6095 ms 349204 KB Output is correct
27 Execution timed out 8004 ms 388176 KB Time limit exceeded
28 Halted 0 ms 0 KB -