제출 #89855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89855		Ruffy	공장들 (JOI14_factories)	C++14	100 / 100	6431 ms	245464 KiB

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;
////    }
//
//
//}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67