oj.uz

Submission #25301

# Submission time Handle Problem Language Result Execution time Memory
25301 2017-06-21T06:08:12 Z 시제연(#1061) Factories (JOI14_factories) C++
15 / 100
 6000 ms 177816 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];
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;
    for (i=0;i<lis[cen].size();i++) {
        int there = lis[cen][i].second;
        if (dead[there]) continue;
        cendc(there,step+1);
    }
    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 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 fin = en[beg], st = stp[idx], i, j, p;
    ll minix = (1LL<<60), miniy = (1LL<<60);
    for (i=sx;i<ex;i++) minix = min(minix,dep[st][x[i]]);
    for (i=sy;i<ey;i++) miniy = min(miniy,dep[st][y[i]]);
    ll res = minix+miniy;
    i=sx; j=sy;
    if (x[i]==idx) i++;
    if (y[j]==idx) j++;
    p = beg+1;
    while(p<fin) {
        int q = en[p], ti = i, tj = j;
        while(ti<ex&&num[x[ti]]<q) ti++;
        while(tj<ey&&num[y[tj]]<q) tj++;
        res = min(res,dnc(i,ti,j,tj,ord[p]));
        i = ti; j = tj; p = q;
    }
    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:19: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:29: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:48: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:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[cen].size();i++) {
               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 136132 KB Output is correct
2 Correct 606 ms 136396 KB Output is correct
3 Correct 616 ms 136396 KB Output is correct
4 Correct 569 ms 136396 KB Output is correct
5 Correct 626 ms 136480 KB Output is correct
6 Correct 606 ms 136420 KB Output is correct
7 Correct 539 ms 136396 KB Output is correct
8 Correct 549 ms 136396 KB Output is correct
9 Correct 609 ms 136476 KB Output is correct
10 Correct 663 ms 136420 KB Output is correct
11 Correct 569 ms 136396 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 136132 KB Output is correct
2 Correct 2516 ms 161740 KB Output is correct
3 Correct 3699 ms 165268 KB Output is correct
4 Execution timed out 6000 ms 159928 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3129 ms 161740 KB Output is correct
2 Correct 2866 ms 161740 KB Output is correct
3 Correct 4593 ms 164532 KB Output is correct
4 Correct 4246 ms 164956 KB Output is correct
5 Correct 4606 ms 164860 KB Output is correct
6 Correct 5369 ms 177816 KB Output is correct
7 Execution timed out 6000 ms 159928 KB Execution timed out
8 Halted 0 ms 0 KB -