답안 #74254 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74254	2018-08-30T16:02:26 Z	Pajaraja	공장들 (JOI14_factories)	C++17	33 / 100	8000 ms	388176 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[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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #74254

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 18.0 / 18.0

Subtask #3 0 / 67.0

Subtask #1
15.0 / 15.0

Subtask #2
18.0 / 18.0

Subtask #3
0 / 67.0