Submission #313105

#	Time	Username	Problem	Language	Result	Execution time	Memory
313105		mohamedsobhi777	Cities (BOI16_cities)	C++14	0 / 100	184 ms	25516 KiB

cities

#include<bits/stdc++.h>

/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 2e5 + 7 , mod = 1e9 + 7 ; 
const int inf = N ; 
// How interesting!

int n , k , m; 
bool imp[N] ; 
int fat[N] ; 
vector<pair<int,pii>> ed;
vector<pii> adj[N] ;  
int st[N], en[N] , t; 
int up[N][20] ; 
ll pref[N] ; 
ll ans ; 

inline int find(int x){return fat[x] = (x == fat[x] ? x : find(fat[x])) ; }
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] ; }

void link(int u , int v, int c){
        int u0 = u , v0 = v ; 
        u = find(u) ; 
        v = find(v) ; 
        if(u != v){
                fat[u] = v ; 
                adj[u0].push_back({v0 , c}) ;
                adj[v0].push_back({u0 , c}) ; 
        }
}

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

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 build(vector<int> &vec){
        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) ; 

        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) ){
                        int u = aux[aux.size() - 2]; 
                        int v = aux.back();
                        ans += pref[v] - pref[u] ; 
                        aux.pop_back() ; 
                }
                aux.push_back(j) ; 
        }
        while(aux.size() > 1){
                int u = aux[aux.size() - 2]; 
                int v = aux.back();
                ans += pref[v] - pref[u] ;
                aux.pop_back() ; 
        }
}

int main(){

        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin >> n >> k >> m ;
        vector<int> vec ; 
        for(int i = 0 ;i < N ; ++ i)
                fat[i] = i ; 

        for(int i = 0 ;i < k ; ++ i){
                int x; cin >> x; 
                vec.push_back(x) ; 
                imp[x] = 1; 
        }

        for(int i = 0 ;i < m; ++ i){
                int u , v , c; 
                cin >> u >> v >> c ; 
                ed.push_back({c,{u , v}}) ; 
        }

        sort(ed.begin(), ed.end()) ; 
        for(auto u : ed){
                link(u.second.first , u.second.second, u.first) ;
        }
        dfs(1 , 1) ;
        build(vec) ;  
        cout<< ans; 
        return 0 ; 
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26