oj.uz

답안 #310424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310424 2020-10-06T21:58:01 Z mohamedsobhi777 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 114192 KB 
#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] ; 
int _n; 

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], nerst[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 dfz2(int x, int p){
        long long ret = 1e18 ; 
        if( (col[x]&1) )ret = 0 ; 

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

        return nerst[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) == 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(), cmp) ; 
        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) ; 
        dfz2(0 , 0) ; 
        for(int i = 0 ;i < _n ; ++ i)
                answer = min(answer , nrst[i] + nerst[i]) ; 

        for(auto u : vec){
                col[u] = 0 ; 
                adx[u].clear() ; 
                nrst[u] = nerst[u] = 1e18 ; 
        }
        return answer ;
}

void Init(int N, int A[], int B[], int D[]) {
        _n = N ; 
        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}) ; 
        }
        fill(nrst , nrst + N , 1e18) ; 
        fill(nerst , nerst + N , 1e18) ; 
        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) ; 
        return answer ; 
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 24192 KB Output is correct
2 Correct 1308 ms 33016 KB Output is correct
3 Correct 1285 ms 33016 KB Output is correct
4 Correct 1280 ms 33272 KB Output is correct
5 Correct 1038 ms 33148 KB Output is correct
6 Correct 949 ms 32932 KB Output is correct
7 Correct 1234 ms 33040 KB Output is correct
8 Correct 1264 ms 33272 KB Output is correct
9 Correct 1039 ms 33272 KB Output is correct
10 Correct 944 ms 33064 KB Output is correct
11 Correct 1232 ms 33016 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 24064 KB Output is correct
2 Execution timed out 8023 ms 114192 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 24192 KB Output is correct
2 Correct 1308 ms 33016 KB Output is correct
3 Correct 1285 ms 33016 KB Output is correct
4 Correct 1280 ms 33272 KB Output is correct
5 Correct 1038 ms 33148 KB Output is correct
6 Correct 949 ms 32932 KB Output is correct
7 Correct 1234 ms 33040 KB Output is correct
8 Correct 1264 ms 33272 KB Output is correct
9 Correct 1039 ms 33272 KB Output is correct
10 Correct 944 ms 33064 KB Output is correct
11 Correct 1232 ms 33016 KB Output is correct
12 Correct 18 ms 24064 KB Output is correct
13 Execution timed out 8023 ms 114192 KB Time limit exceeded
14 Halted 0 ms 0 KB -