답안 #89860 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89860	2018-12-18T15:47:48 Z	Ruffy	공장들 (JOI14_factories)	C++14	100 / 100	5439 ms	158620 KB

factories

//#include "factories.h"
#include <bits/stdc++.h>

#define MEM(a, b) memset(a, (b), sizeof(a))
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef std::pair<int, int> pii;

const ll INF = 0x3f3f3f3f3f3f3f3f;
#define MAXN 500000
using namespace std;
vector<pii> a[MAXN];
//vector<int> b[MAXN];
bool done[MAXN];
int sz[MAXN], par[MAXN];
char lvl[MAXN];
ll d[MAXN][19];
ll ans[MAXN];
void dfs(int cur, int last){
    sz[cur] = 1;
    for(pii i : a[cur]){
        if(i.f!= last && !done[i.f]){
            dfs(i.f,cur); sz[cur]+=sz[i.f];
        }
    }
}
int Cen(int cur, int last, int tot){
    for(pii i : a[cur]){
        if(i.f == last || done[i.f]) continue;
        if(sz[i.f]<<1 > tot){
            return Cen(i.f, cur, tot);
        }
    }
    return cur;
}

void minDis(int cur, int last, ll dis, char lvl){
    d[cur][lvl] = dis;
    for(pii i : a[cur]){
        if(i.f==last||done[i.f]) continue;
        minDis(i.f,cur,dis+i.s,lvl);
    }
}

int decomp(int rt, char lv){
    dfs(rt, -1);
    int cen = Cen(rt, -1, sz[rt]);
    done[cen] = 1;

    lvl[cen] = lv;
    minDis(cen,-1,0,lv);
    for(pii i : a[cen]){
        if(!done[i.f]){
            int sub = decomp(i.f, lv + 1);
            par[sub] = cen;
//            b[cen].pb(sub);
//            b[sub].pb(cen)    ;
        }
    }
    return cen;
}

/*
16 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 4 2 4 3 4 4 5 5 6 6 7 7 8 7 9 6 10 10 11 11 12 11 13 12 14 13 15 13 16
*/

void Init(int N, int A[], int B[], int D[]){
    MEM(ans, INF);
    for(int i = 0; i < N-1; i++){
        a[A[i]].pb({B[i],D[i]});
        a[B[i]].pb({A[i],D[i]});
    }
    par[decomp(1,0)] = -1;
}

long long Query(int S, int X[], int T, int Y[]){
    for(int k = 0; k < S; k++){
        int cur = X[k];
        while(cur!=-1){
            ans[cur] = min(ans[cur],d[X[k]][lvl[cur]]);
            cur = par[cur];
        }
    }

    ll ret = INF;
    for(int k = 0; k < T; k++){
        int cur = Y[k];
        while(cur!=-1){
            ret = min(ret, ans[cur] + d[Y[k]][lvl[cur]]);
            //cout<<cur<<endl;
            cur = par[cur];
        }
    }
    for(int k = 0; k < S; k++){
        int cur = X[k];
        while(cur!=-1){
            ans[cur] = INF;
            cur = par[cur];
        }
    }
    //cout<<endl;
    return ret;
}
//
//int main(){
//    cin.sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
////    int n,q;
////    cin>>n>>q;
////    int a[n], b[n],d2[n];
////    for(int i = 0; i < n-1;i++){
////        cin>>a[i]>>b[i]>>d2[i];
////    }
////    Init(n,a,b,d2);
//////    for(int i = 0; i < n; i++){
//////        cout<<lvl[i]<<endl;
//////    }
//////    while(1){
//////        int x,y;
//////        cin>>x>>y;
//////        cout<<d[x][y]<<endl;
//////    }
////
////    int s,t;
////    for(int i = 0; i < q; i++){
////        cin>>s>>t;
////        int x[s], y[t];
////        for(int j = 0; j < s; j++){
////            cin>>x[j];
////        }
////        for(int j = 0; j < t; j++){
////            cin>>y[j];
////        }
////        cout<<Query(s,x,t,y)<<endl;
////    }
//
//
//}

Compilation message

factories.cpp: In function 'void minDis(int, int, ll, char)':
factories.cpp:40:15: warning: array subscript has type 'char' [-Wchar-subscripts]
     d[cur][lvl] = dis;
               ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:72:14: warning: overflow in implicit constant conversion [-Woverflow]
factories.cpp:4:29:
 #define MEM(a, b) memset(a, (b), sizeof(a))
                             ~~~
factories.cpp:72:14:
     MEM(ans, INF);
factories.cpp:4:30: note: in definition of macro 'MEM'
 #define MEM(a, b) memset(a, (b), sizeof(a))
                              ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:84:53: warning: array subscript has type 'char' [-Wchar-subscripts]
             ans[cur] = min(ans[cur],d[X[k]][lvl[cur]]);
                                                     ^
factories.cpp:93:55: warning: array subscript has type 'char' [-Wchar-subscripts]
             ret = min(ret, ans[cur] + d[Y[k]][lvl[cur]]);
                                                       ^

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	16376 KB	Output is correct
2	Correct	373 ms	25292 KB	Output is correct
3	Correct	418 ms	25384 KB	Output is correct
4	Correct	393 ms	25384 KB	Output is correct
5	Correct	429 ms	25520 KB	Output is correct
6	Correct	294 ms	25520 KB	Output is correct
7	Correct	412 ms	25520 KB	Output is correct
8	Correct	404 ms	25520 KB	Output is correct
9	Correct	414 ms	25520 KB	Output is correct
10	Correct	311 ms	25520 KB	Output is correct
11	Correct	423 ms	25520 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	25520 KB	Output is correct
2	Correct	2617 ms	127136 KB	Output is correct
3	Correct	4254 ms	128076 KB	Output is correct
4	Correct	1152 ms	128076 KB	Output is correct
5	Correct	5439 ms	151668 KB	Output is correct
6	Correct	4295 ms	151668 KB	Output is correct
7	Correct	1224 ms	151668 KB	Output is correct
8	Correct	552 ms	151668 KB	Output is correct
9	Correct	1412 ms	151668 KB	Output is correct
10	Correct	1259 ms	151668 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	16376 KB	Output is correct
2	Correct	373 ms	25292 KB	Output is correct
3	Correct	418 ms	25384 KB	Output is correct
4	Correct	393 ms	25384 KB	Output is correct
5	Correct	429 ms	25520 KB	Output is correct
6	Correct	294 ms	25520 KB	Output is correct
7	Correct	412 ms	25520 KB	Output is correct
8	Correct	404 ms	25520 KB	Output is correct
9	Correct	414 ms	25520 KB	Output is correct
10	Correct	311 ms	25520 KB	Output is correct
11	Correct	423 ms	25520 KB	Output is correct
12	Correct	19 ms	25520 KB	Output is correct
13	Correct	2617 ms	127136 KB	Output is correct
14	Correct	4254 ms	128076 KB	Output is correct
15	Correct	1152 ms	128076 KB	Output is correct
16	Correct	5439 ms	151668 KB	Output is correct
17	Correct	4295 ms	151668 KB	Output is correct
18	Correct	1224 ms	151668 KB	Output is correct
19	Correct	552 ms	151668 KB	Output is correct
20	Correct	1412 ms	151668 KB	Output is correct
21	Correct	1259 ms	151668 KB	Output is correct
22	Correct	2987 ms	151668 KB	Output is correct
23	Correct	2862 ms	151668 KB	Output is correct
24	Correct	4183 ms	151668 KB	Output is correct
25	Correct	3804 ms	151668 KB	Output is correct
26	Correct	3749 ms	151668 KB	Output is correct
27	Correct	4820 ms	158620 KB	Output is correct
28	Correct	1375 ms	158620 KB	Output is correct
29	Correct	4687 ms	158620 KB	Output is correct
30	Correct	4607 ms	158620 KB	Output is correct
31	Correct	4567 ms	158620 KB	Output is correct
32	Correct	1483 ms	158620 KB	Output is correct
33	Correct	547 ms	158620 KB	Output is correct
34	Correct	802 ms	158620 KB	Output is correct
35	Correct	821 ms	158620 KB	Output is correct
36	Correct	1159 ms	158620 KB	Output is correct
37	Correct	1141 ms	158620 KB	Output is correct

답안 #89860

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