| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25320 |
2017-06-21T06:58:35 Z |
시제연(#1061) |
Factories (JOI14_factories) |
C++ |
|
3026 ms |
524288 KB |
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
int n;
vector<pli> lis[500100];
int sz[500100];
int num[500100], en[500100], ord[500100], stp[500100];
ll dep[22][500100];
vector<int> st[500100];
bool dead[500100];
int idfs(int here, int p) {
int i;
sz[here] = 1;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].second;
if (dead[there]||there==p) continue;
sz[here] += idfs(there,here);
}
return sz[here];
}
int cdfs(int here, int p, int asz) {
int i, maxi = -1, t = -1;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].second;
if (dead[there]||there==p) continue;
if (maxi<sz[there]) {
maxi = sz[there];
t = there;
}
}
if (maxi<=asz/2) return here;
else return cdfs(t,here,asz);
}
int findcen(int head) {
return cdfs(head,-1,idfs(head,-1));
}
void adfs(int here, int p, ll d, int step) {
int i;
dep[step][here] = d;
for (i=0;i<lis[here].size();i++) {
int there = lis[here][i].second;
if (there==p||dead[there]) continue;
adfs(there,here,d+lis[here][i].first,step);
}
}
int tt;
void cendc(int head, int step) {
int cen = findcen(head), i;
stp[cen] = step;
num[cen] = tt;
ord[tt++] = cen;
adfs(cen,-1,0,step);
dead[cen] = true;
st[cen].push_back(num[cen]);
for (i=0;i<lis[cen].size();i++) {
int there = lis[cen][i].second;
if (dead[there]) continue;
cendc(there,step+1);
st[cen].push_back(num[there]);
}
en[num[cen]] = tt;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
int i;
for (i=0;i<n-1;i++) {
lis[A[i]].push_back(pli(D[i],B[i]));
lis[B[i]].push_back(pli(D[i],A[i]));
}
cendc(0,0);
}
int xl[500100], yl[500100];
int x[500100], y[500100];
ll dnc(int sx, int ex, int sy, int ey, int idx) {
if (sx>=ex||sy>=ey) return (1LL<<60);
int beg = num[idx]; int stt = stp[idx], i, j;
ll minix = (1LL<<60), miniy = (1LL<<60);
for (i=sx;i<ex;i++) minix = min(minix,dep[stt][x[i]]);
for (i=sx;i<ex;i++) xl[i] = *(--upper_bound(st[idx].begin(),st[idx].end(),num[x[i]]));
for (i=sy;i<ey;i++) miniy = min(miniy,dep[stt][y[i]]);
for (i=sy;i<ey;i++) yl[i] = *(--upper_bound(st[idx].begin(),st[idx].end(),num[y[i]]));
ll res = minix+miniy;
i=sx; j=sy;
if (x[i]==idx) i++;
if (y[j]==idx) j++;
int ti = i, tj = j;
for (;i<ex;i++) {
if (i==ex-1||xl[i+1]!=xl[i]) {
for (;j<ey&&yl[j]<xl[i];j++);
tj = j;
for (;j<ey&&yl[j]==xl[i];j++);
res = min(res,dnc(ti,i+1,tj,j,ord[xl[i]]));
ti = i+1; tj = j;
}
}
return res;
}
bool cmp(int a, int b) {return num[a]<num[b];}
ll Query(int S, int X[], int T, int Y[]) {
int i;
for (i=0;i<S;i++) x[i] = X[i];
for (i=0;i<T;i++) y[i] = Y[i];
sort(x,x+S,cmp);
sort(y,y+T,cmp);
return dnc(0,S,0,T,ord[0]);
}
Compilation message
factories.cpp: In function 'int idfs(int, int)':
factories.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
factories.cpp: In function 'int cdfs(int, int, int)':
factories.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
factories.cpp: In function 'void adfs(int, int, ll, int)':
factories.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[here].size();i++) {
^
factories.cpp: In function 'void cendc(int, int)':
factories.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<lis[cen].size();i++) {
^
factories.cpp: In function 'll dnc(int, int, int, int, int)':
factories.cpp:88:9: warning: unused variable 'beg' [-Wunused-variable]
int beg = num[idx]; int stt = stp[idx], i, j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
339 ms |
524288 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
129 ms |
524288 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
3026 ms |
524288 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
