oj.uz

Submission #310391

# Submission time Handle Problem Language Result Execution time Memory
310391 2020-10-06T20:21:02 Z mohamedsobhi777 Factories (JOI14_factories) C++14
18 / 100
 8000 ms 140432 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] ; 

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() ; 
        }
        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 ; 
}

Compilation message

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]) ;
      |                   ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 24192 KB Output is correct
2 Execution timed out 8009 ms 41976 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 1602 ms 123036 KB Output is correct
3 Correct 4037 ms 123184 KB Output is correct
4 Correct 1252 ms 123368 KB Output is correct
5 Correct 1647 ms 140432 KB Output is correct
6 Correct 3105 ms 125112 KB Output is correct
7 Correct 5122 ms 62148 KB Output is correct
8 Correct 1820 ms 62972 KB Output is correct
9 Correct 1655 ms 65268 KB Output is correct
10 Correct 3041 ms 63548 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 24192 KB Output is correct
2 Execution timed out 8009 ms 41976 KB Time limit exceeded
3 Halted 0 ms 0 KB -