Submission #30531

#	Time	Username	Problem	Language	Result	Execution time	Memory
30531		tlwpdus	Factories (JOI14_factories)	C++11	15 / 100	6000 ms	218876 KiB

factories

#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;
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 (stderr)

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 'int 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;
         ^

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67