# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
285258 |
2020-08-28T14:02:35 Z |
YJU |
Factories (JOI14_factories) |
C++14 |
|
8000 ms |
166052 KB |
#include<bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
int parent[N],sz[N],ms[N],lv[N],K,lis[N],L;
vector<pll> v[N];
ll dist[N][25],dis[N];
void buildd(int id,int par){
for(pll i:v[id]){
if(i.X==par||lv[i.X]!=-1)continue;
dist[i.X][L]=i.Y+dist[id][L];
buildd(i.X,id);
}
}
void DFS(int id,int par){
sz[id]=1;ms[id]=0;
for(pll i:v[id]){
if(i.X==par||lv[i.X]!=-1)continue;
DFS(i.X,id);
sz[id]+=sz[i.X];
ms[id]=max(ms[id],sz[i.X]);
}
lis[K++]=id;
}
void buildc(int nd,int pa){
K=0;
DFS(nd,0);
ll cho=lis[0];
REP(i,K){
if(max(ms[cho],sz[nd]-sz[cho])>max(ms[lis[i]],sz[nd]-ms[lis[i]]))cho=lis[i];
}
parent[cho]=pa;
L=lv[cho]=lv[pa]+1;
buildd(cho,0);
for(pll i:v[cho]){
if(lv[i.X]!=-1||i.X==pa)continue;
buildc(i.X,cho);
}
}
void Init(int n,int A[],int B[],int D[]){
REP1(i,n)dis[i]=INF;
REP(i,n)++A[i],++B[i],lv[i+1]=-1;
REP(i,n-1){
v[B[i]].pb(mp(A[i],D[i]));
v[A[i]].pb(mp(B[i],D[i]));
}
buildc(1,0);
}
ll Query(int S,int x[],int T,int y[]){
ll ans=INF;
REP(i,S)++x[i];REP(i,T)++y[i];
REP(i,S){
ll nd=x[i];
while(nd){
dis[nd]=min(dis[nd],dist[x[i]][lv[nd]]);
nd=parent[nd];
}
}
REP(i,T){
ll nd=y[i];
while(nd){
ans=min(ans,dis[nd]+dist[y[i]][lv[nd]]);
nd=parent[nd];
}
}
REP(i,S){
ll nd=x[i];
while(nd){
dis[nd]=INF;
nd=parent[nd];
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
12544 KB |
Output is correct |
2 |
Correct |
411 ms |
21624 KB |
Output is correct |
3 |
Correct |
435 ms |
21624 KB |
Output is correct |
4 |
Correct |
425 ms |
21624 KB |
Output is correct |
5 |
Correct |
439 ms |
22172 KB |
Output is correct |
6 |
Execution timed out |
8018 ms |
21752 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12416 KB |
Output is correct |
2 |
Correct |
2531 ms |
162168 KB |
Output is correct |
3 |
Correct |
3612 ms |
166052 KB |
Output is correct |
4 |
Execution timed out |
8061 ms |
156628 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
12544 KB |
Output is correct |
2 |
Correct |
411 ms |
21624 KB |
Output is correct |
3 |
Correct |
435 ms |
21624 KB |
Output is correct |
4 |
Correct |
425 ms |
21624 KB |
Output is correct |
5 |
Correct |
439 ms |
22172 KB |
Output is correct |
6 |
Execution timed out |
8018 ms |
21752 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |