oj.uz

Submission #25541

# Submission time Handle Problem Language Result Execution time Memory
25541 2017-06-23T00:37:49 Z tlwpdus Factories (JOI14_factories) C++
33 / 100
 6000 ms 212164 KB 
#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;
int 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;
        st[cen].push_back(num[cendc(there,step+1)]);
    }
    en[num[cen]] = tt;
    return cen;
}

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: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 'int cendc(int, int)':
factories.cpp:64: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:87:9: warning: unused variable 'beg' [-Wunused-variable]
     int beg = num[idx]; int stt = stp[idx], i, j;
         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 151760 KB Output is correct
2 Correct 683 ms 152156 KB Output is correct
3 Correct 773 ms 152156 KB Output is correct
4 Correct 549 ms 152156 KB Output is correct
5 Correct 766 ms 152240 KB Output is correct
6 Correct 666 ms 152312 KB Output is correct
7 Correct 739 ms 152156 KB Output is correct
8 Correct 576 ms 152156 KB Output is correct
9 Correct 816 ms 152240 KB Output is correct
10 Correct 679 ms 152312 KB Output is correct
11 Correct 723 ms 152156 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 151760 KB Output is correct
2 Correct 2773 ms 193736 KB Output is correct
3 Correct 4236 ms 195680 KB Output is correct
4 Correct 1429 ms 193256 KB Output is correct
5 Correct 5273 ms 212164 KB Output is correct
6 Correct 4409 ms 195356 KB Output is correct
7 Correct 1333 ms 160456 KB Output is correct
8 Correct 913 ms 160620 KB Output is correct
9 Correct 1366 ms 162808 KB Output is correct
10 Correct 1409 ms 160384 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3409 ms 193736 KB Output is correct
2 Correct 2863 ms 193736 KB Output is correct
3 Correct 5473 ms 194944 KB Output is correct
4 Correct 5233 ms 195376 KB Output is correct
5 Correct 5293 ms 195268 KB Output is correct
6 Execution timed out 6000 ms 207832 KB Execution timed out
7 Halted 0 ms 0 KB -