답안 #89855 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89855	2018-12-18T15:30:16 Z	Ruffy	공장들 (JOI14_factories)	C++14	100 / 100	6431 ms	245464 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[19][MAXN];
ll ans[MAXN];
stack<int> changed;
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[lvl][cur] = 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){
            changed.push(cur);
            ans[cur] = min(ans[cur],d[lvl[cur]][X[k]]);
            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[lvl[cur]][Y[k]]);
            //cout<<cur<<endl;
            cur = par[cur];
        }
    }
    while(!changed.empty()){
        ans[changed.top()] = INF;
        changed.pop();
    }
    //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:41:10: warning: array subscript has type 'char' [-Wchar-subscripts]
     d[lvl][cur] = dis;
          ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:73:14: warning: overflow in implicit constant conversion [-Woverflow]
factories.cpp:4:29:
 #define MEM(a, b) memset(a, (b), sizeof(a))
                             ~~~
factories.cpp:73: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:86:47: warning: array subscript has type 'char' [-Wchar-subscripts]
             ans[cur] = min(ans[cur],d[lvl[cur]][X[k]]);
                                               ^
factories.cpp:95:49: warning: array subscript has type 'char' [-Wchar-subscripts]
             ret = min(ret, ans[cur] + d[lvl[cur]][Y[k]]);
                                                 ^

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	16632 KB	Output is correct
2	Correct	411 ms	34488 KB	Output is correct
3	Correct	426 ms	44044 KB	Output is correct
4	Correct	439 ms	53712 KB	Output is correct
5	Correct	465 ms	60948 KB	Output is correct
6	Correct	283 ms	60948 KB	Output is correct
7	Correct	409 ms	60948 KB	Output is correct
8	Correct	428 ms	61016 KB	Output is correct
9	Correct	441 ms	61144 KB	Output is correct
10	Correct	295 ms	61144 KB	Output is correct
11	Correct	410 ms	61144 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	61144 KB	Output is correct
2	Correct	2794 ms	147548 KB	Output is correct
3	Correct	4928 ms	163872 KB	Output is correct
4	Correct	1000 ms	163872 KB	Output is correct
5	Correct	6431 ms	187144 KB	Output is correct
6	Correct	4969 ms	187144 KB	Output is correct
7	Correct	1476 ms	187144 KB	Output is correct
8	Correct	434 ms	187144 KB	Output is correct
9	Correct	1452 ms	187144 KB	Output is correct
10	Correct	1234 ms	187144 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	16632 KB	Output is correct
2	Correct	411 ms	34488 KB	Output is correct
3	Correct	426 ms	44044 KB	Output is correct
4	Correct	439 ms	53712 KB	Output is correct
5	Correct	465 ms	60948 KB	Output is correct
6	Correct	283 ms	60948 KB	Output is correct
7	Correct	409 ms	60948 KB	Output is correct
8	Correct	428 ms	61016 KB	Output is correct
9	Correct	441 ms	61144 KB	Output is correct
10	Correct	295 ms	61144 KB	Output is correct
11	Correct	410 ms	61144 KB	Output is correct
12	Correct	20 ms	61144 KB	Output is correct
13	Correct	2794 ms	147548 KB	Output is correct
14	Correct	4928 ms	163872 KB	Output is correct
15	Correct	1000 ms	163872 KB	Output is correct
16	Correct	6431 ms	187144 KB	Output is correct
17	Correct	4969 ms	187144 KB	Output is correct
18	Correct	1476 ms	187144 KB	Output is correct
19	Correct	434 ms	187144 KB	Output is correct
20	Correct	1452 ms	187144 KB	Output is correct
21	Correct	1234 ms	187144 KB	Output is correct
22	Correct	3500 ms	187144 KB	Output is correct
23	Correct	3531 ms	187144 KB	Output is correct
24	Correct	5454 ms	187144 KB	Output is correct
25	Correct	5919 ms	187144 KB	Output is correct
26	Correct	6006 ms	187144 KB	Output is correct
27	Correct	6047 ms	196356 KB	Output is correct
28	Correct	1002 ms	196356 KB	Output is correct
29	Correct	4754 ms	214772 KB	Output is correct
30	Correct	4674 ms	239960 KB	Output is correct
31	Correct	4649 ms	245464 KB	Output is correct
32	Correct	1499 ms	245464 KB	Output is correct
33	Correct	450 ms	245464 KB	Output is correct
34	Correct	857 ms	245464 KB	Output is correct
35	Correct	916 ms	245464 KB	Output is correct
36	Correct	1233 ms	245464 KB	Output is correct
37	Correct	1309 ms	245464 KB	Output is correct

답안 #89855

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