답안 #52747 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52747	2018-06-26T14:28:15 Z	Smelskiy	공장들 (JOI14_factories)	C++14	100 / 100	5502 ms	377448 KB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;







int n;
int timer;
int x,y;
long long depth[500005];
int dp[500005][22];
long long len[500005][22];
int depth2[500005];
vector<pair<int,long long> > v[500005];
long long dp2[500005];
int pred[500005];
int tin[500005];
int tout[500005];
bool used[500005];
int sz;
int q[500005];
long long ans;

void dfs(int x,int y) {
    tin[x]=++timer;
    dp[x][0]=y;
    for (int i=1;i<=19;++i)
        dp[x][i]=dp[dp[x][i-1]][i-1];
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (to==y) continue;
        depth[to]=depth[x];
        depth[to]+=v[x][i].second;
        dfs(to,x);
    }
    tout[x]=timer;
}

int cnt[500005];
int mx[500005];


void dfs1(int x,int y) {
    q[++sz]=x;
    cnt[x]=1;
    mx[x]=0;
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (to==y || used[to]) continue;
        dfs1(to,x);
        cnt[x]+=cnt[to];
        if (cnt[to]>mx[x]) {
            mx[x]=cnt[to];
        }
    }
}

void dfs3(int x,int y,long long l,int z) {
    len[x][z]=l;
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (to==y || used[to]) continue;
        dfs3(to,x,l+v[x][i].second,z);
    }
}

void build(int x,int y) {
    sz=0;
    dfs1(x,0);
    int mn=1e9;
    int c=x,xx;
    int cur;
    for (int i=1;i<=sz;++i) {
        xx=q[i];
        cur=max(mx[xx],cnt[x]-cnt[xx]);
        if (cur<mn) {
            mn=cur;
            c=xx;
        }
    }
    used[c]=true;
    x=c;
    pred[x]=y;
    depth2[x]=depth2[y]+1;
    dfs3(x,0,0,depth2[x]);
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (!used[to]) build(to,x);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    int z;
    for (int i=0;i<n-1;++i) {
        x=A[i];
        y=B[i];
        ++x; ++y;
        z=D[i];
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    dfs(1,0);
    build(1,0);
    for (int i=1;i<=n;++i)
        dp2[i]=1e15;
}

bool f_pred(int x,int y) {
    return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}

inline int get_lca(int x,int y) {
    if (f_pred(x,y)) return x;
    if (f_pred(y,x)) return y;
    for (int i=19;i>=0;--i)
        if (dp[x][i] && !f_pred(dp[x][i],y)) x=dp[x][i];
    return dp[x][0];
}

inline long long get_dist(int x,int y) {
    return len[x][depth2[y]];
}

inline void update1(int x) {
    int y=x;
    long long xx;
    while (y) {
        xx=get_dist(x,y);
        if (xx<dp2[y]) dp2[y]=xx;
        y=pred[y];
    }
}
inline void update2(int x) {
    while (x) {
        if (dp2[x]==1e15) return;
        dp2[x]=1e15;
        x=pred[x];
    }
}
inline void solve(int x) {
    int y=x;
    long long xx;
    while (y) {
        xx=get_dist(x,y)+dp2[y];
        if (xx<ans) ans=xx;
        y=pred[y];
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ans=1e18;
    int x;
    for (int i=0;i<S;++i) {
        x=X[i];
        ++x;
        update1(x);
    }
    for (int i=0;i<T;++i) {
        x=Y[i];
        ++x;
        solve(x);
    }
    for (int i=-0;i<S;++i) {
        x=X[i];
        ++x;
        update2(x);
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs1(int, int)':
factories.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs3(int, int, long long int, int)':
factories.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
factories.cpp: In function 'void build(int, int)':
factories.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	12664 KB	Output is correct
2	Correct	453 ms	22300 KB	Output is correct
3	Correct	431 ms	22368 KB	Output is correct
4	Correct	391 ms	22368 KB	Output is correct
5	Correct	428 ms	22532 KB	Output is correct
6	Correct	326 ms	22532 KB	Output is correct
7	Correct	487 ms	22532 KB	Output is correct
8	Correct	450 ms	22532 KB	Output is correct
9	Correct	479 ms	22704 KB	Output is correct
10	Correct	287 ms	22704 KB	Output is correct
11	Correct	430 ms	22704 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	22704 KB	Output is correct
2	Correct	3090 ms	202140 KB	Output is correct
3	Correct	4575 ms	205264 KB	Output is correct
4	Correct	1433 ms	205264 KB	Output is correct
5	Correct	5502 ms	229916 KB	Output is correct
6	Correct	4298 ms	229916 KB	Output is correct
7	Correct	1332 ms	229916 KB	Output is correct
8	Correct	609 ms	229916 KB	Output is correct
9	Correct	1643 ms	229916 KB	Output is correct
10	Correct	1278 ms	229916 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	12664 KB	Output is correct
2	Correct	453 ms	22300 KB	Output is correct
3	Correct	431 ms	22368 KB	Output is correct
4	Correct	391 ms	22368 KB	Output is correct
5	Correct	428 ms	22532 KB	Output is correct
6	Correct	326 ms	22532 KB	Output is correct
7	Correct	487 ms	22532 KB	Output is correct
8	Correct	450 ms	22532 KB	Output is correct
9	Correct	479 ms	22704 KB	Output is correct
10	Correct	287 ms	22704 KB	Output is correct
11	Correct	430 ms	22704 KB	Output is correct
12	Correct	14 ms	22704 KB	Output is correct
13	Correct	3090 ms	202140 KB	Output is correct
14	Correct	4575 ms	205264 KB	Output is correct
15	Correct	1433 ms	205264 KB	Output is correct
16	Correct	5502 ms	229916 KB	Output is correct
17	Correct	4298 ms	229916 KB	Output is correct
18	Correct	1332 ms	229916 KB	Output is correct
19	Correct	609 ms	229916 KB	Output is correct
20	Correct	1643 ms	229916 KB	Output is correct
21	Correct	1278 ms	229916 KB	Output is correct
22	Correct	3087 ms	229916 KB	Output is correct
23	Correct	3223 ms	229916 KB	Output is correct
24	Correct	4838 ms	229916 KB	Output is correct
25	Correct	4731 ms	235204 KB	Output is correct
26	Correct	4841 ms	256300 KB	Output is correct
27	Correct	5467 ms	301776 KB	Output is correct
28	Correct	1445 ms	302320 KB	Output is correct
29	Correct	4670 ms	329716 KB	Output is correct
30	Correct	5011 ms	353396 KB	Output is correct
31	Correct	4683 ms	377448 KB	Output is correct
32	Correct	1353 ms	377448 KB	Output is correct
33	Correct	535 ms	377448 KB	Output is correct
34	Correct	894 ms	377448 KB	Output is correct
35	Correct	947 ms	377448 KB	Output is correct
36	Correct	1154 ms	377448 KB	Output is correct
37	Correct	1267 ms	377448 KB	Output is correct

답안 #52747

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 18.0 / 18.0

Subtask #3 67.0 / 67.0

Subtask #1
15.0 / 15.0

Subtask #2
18.0 / 18.0

Subtask #3
67.0 / 67.0