제출 #310392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310392		mohamedsobhi777	Factories (JOI14_factories)	C++14	0 / 100	123 ms	28280 KiB

factories

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

const int MX = 5e5 + 7 ; 
using namespace std ; 

vector<pair<int,int> > adj[MX];
vector<int> adx[MX];
int st[MX], en[MX] , t ; 
int up[MX][20] ; 
int col[MX] ; 
long long pref[MX] ; 

void dfs(int x, int p ){
        st[x] = ++ t ; 
        up[x][0] = p ; 
        for(int i = 1; i < 20 ; ++ i)
                up[x][i] = up[ up[x][i-1]][i-1] ; 
        for(auto u : adj[x]){
                if(u.first == p)continue ;
                pref[u.first] = pref[x] + u.second ;  
                dfs(u.first , x) ; 
        }
        en[x] = ++ t; 
}

inline bool upper(int u , int v){return st[u] <= st[v] && en[v] <= en[u] ;}
inline bool cmp(int u ,int v){return st[u] < st[v] ;}

int lca(int u ,int v){
        if(upper(u , v))return u ; 
        if(upper(v , u))return v ; 
        for(int i = 19 ; ~ i; -- i){
                if(!upper(up[u][i] , v))
                        u = up[u][i] ; 
        }
        return up[u][0] ; 
}

void edge(int u , int v){
        adx[u].push_back(v) ; 
        adx[v].push_back(u) ; 
}

long long nrst[MX] ; 

long long dfz(int x, int p){
        long long ret = 1e18 ; 
        if(col[x]&2)ret = 0 ; 

        for(auto u : adx[x]){
                if(u == p)continue ; 
                ret = min(ret , pref[u] - pref[x] + dfz(u , x)) ; 
        }

        return nrst[x] = ret ; 
}

long long answer = 0 ; 

long long solve(int x, int p, long long ner = 1e18 ){
        long long ret = (col[x]&1 == 1 ? nrst[x] : 1e18)  ; 
        for(auto u : adx[x]){
                if(u == p)continue; 
                long long add = 1e18 ; 
                for(auto j : adx[x]){
                        if(j == p || j == u)continue ; 
                        add = min(add , nrst[j] + pref[j] - pref[x]) ; 
                }
                ret = min(ret , solve(u , x, min(ner,add )  + pref[u] - pref[x] ) ) ; 

        }
        if(col[x]&1){
                answer = min(answer, min(ret , ner)) ; 
        }
        return ret;
}

long long build(vector<int> &vec){
        answer = 1e18 ; 
        vec.push_back(0) ; 
        int sz = (int) vec.size() ; 
        sort(vec.begin() , vec.end() , cmp) ;
        for(int i = 1; i < sz; ++ i){
                vec.push_back(lca(vec[i-1] , vec[i])) ; 
        }
        sort(vec.begin() , vec.end()) ; 
        vec.erase(unique(vec.begin() , vec.end()) , vec.end()) ;
        vector<int> aux = {vec[0]} ; 

        for(int i = 1; i < (int) vec.size() ; ++ i){
                int j = vec[i] ; 
                while(aux.size() > 1 && !upper(aux.back() ,j) ){
                        edge( aux[aux.size() - 2] , aux.back() ) ; 
                        aux.pop_back() ;
                }
                aux.push_back(j) ; 
        }

        while(aux.size() > 1){
                edge(aux[aux.size() - 2] , aux.back()) ; 
                aux.pop_back() ; 
        }
        dfz(0 , 0) ; 
        long long ret = solve(aux[0] , aux[0]) ; 
        for(auto u : vec){
                col[u] = 0 ; 
                adx[u].clear() ; 
        }
        memset(nrst , 0 , sizeof nrst) ; 
        return answer ;
}

void Init(int N, int A[], int B[], int D[]) {
        for(int i = 0 ;i < N - 1; ++ i){
                int u = A[i] , v = B[i] , w = D[i] ; 
                adj[u].push_back({v , w}) ; 
                adj[v].push_back({u , w}) ; 
        }
        dfs(0 , 0) ; 
}

long long Query(int S, int X[], int T, int Y[]) {
        vector<int> vec ; 
        for(int i = 0 ;i < S ; ++ i){
                col[X[i]]|=1;
                vec.push_back(X[i]) ; 
        }
        for(int i = 0 ;i < T ; ++ i){
                vec.push_back(Y[i]) ; 
                col[Y[i]]|=2;
        }
        build(vec) ; 
        long long ret = 1e18 ; 
        /*for(int i = 0 ; i < S ; ++ i){
                for(int j = 0 ;j < T ; ++ j){
                        int lc = lca(X[i] , Y[j]) ; 
                        ret = min(ret , pref[X[i]] + pref[Y[j]] - 2 * pref[lc]) ; 
                }       
        }
        return ret ; */
        return answer ; 
}

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

factories.cpp: In function 'long long int solve(int, int, long long int)':
factories.cpp:63:35: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   63 |         long long ret = (col[x]&1 == 1 ? nrst[x] : 1e18)  ;
      |                                 ~~^~~~
factories.cpp: In function 'long long int build(std::vector<int>&)':
factories.cpp:106:19: warning: unused variable 'ret' [-Wunused-variable]
  106 |         long long ret = solve(aux[0] , aux[0]) ;
      |                   ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:135:19: warning: unused variable 'ret' [-Wunused-variable]
  135 |         long long ret = 1e18 ;
      |                   ^~~

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