oj.uz

Submission #310087

# Submission time Handle Problem Language Result Execution time Memory
310087 2020-10-05T17:40:39 Z mohamedsobhi777 Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 36032 KB 
#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 ll inf = 2e18 ; 

// How interesting!

int n, m, t ; 
vector<int> adj[N] ; 
int up[N][20] ;
int st[N] , en[N] ; 
vector< pair<pii,int> > vec[N] ;
ll dp[N], kdp[N] ; 
int prv[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 == p)continue ; 
                prv[u] = x; 
                dfs(u , x) ; 
        }
        en[x] = ++ t; 
}

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

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

int walk(int u , int v){
        int ret = 0 ; 

        while(u != v){
                ret += kdp[u] - dp[u] ; 
                u = prv[u] ; 
        }

        return ret; 
}

ll solve(int x, int p){
        ll ret = 0 ; 
        for(auto u : adj[x]){
                if(u == p)continue ; 
                kdp[x] += solve(u , x) ; 
        }

        for(auto u : vec[x]){
                int a = u.first.first ; 
                int b = u.first.second ; 
                int c = u.second ; 
                ret = max(ret , walk(a , x) + walk(b , x) + c + kdp[x]) ; 
        }

        return dp[x] = max(ret , kdp[x]); 
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        cin>> n ; 
        for(int i = 0 ;i < n - 1; ++ i){
                int u , v; 
                cin >> u >> v ; 
                adj[u].push_back(v) ; 
                adj[v].push_back(u) ;
        }
        dfs(1 , 1) ; 
        cin>> m ; 
        for(int i = 0 ; i < m; ++ i){
                int u , v , w ; 
                cin >> u >> v >> w ; 
                int lc = lca(u , v) ; 
                vec[lc].push_back({{u , v}, w}) ;
        }

        solve(1 , 1) ; 
        cout<< dp[1] ; 
        return 0 ; 
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 104 ms 24824 KB Output is correct
6 Correct 60 ms 32376 KB Output is correct
7 Correct 110 ms 29820 KB Output is correct
8 Correct 72 ms 24440 KB Output is correct
9 Correct 105 ms 28180 KB Output is correct
10 Correct 70 ms 24312 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 10016 KB Output is correct
4 Execution timed out 1085 ms 36032 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 10016 KB Output is correct
4 Execution timed out 1085 ms 36032 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 27568 KB Output is correct
2 Execution timed out 1076 ms 35832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 104 ms 24824 KB Output is correct
6 Correct 60 ms 32376 KB Output is correct
7 Correct 110 ms 29820 KB Output is correct
8 Correct 72 ms 24440 KB Output is correct
9 Correct 105 ms 28180 KB Output is correct
10 Correct 70 ms 24312 KB Output is correct
11 Correct 7 ms 9984 KB Output is correct
12 Correct 8 ms 9984 KB Output is correct
13 Correct 8 ms 9984 KB Output is correct
14 Correct 8 ms 9984 KB Output is correct
15 Correct 8 ms 9984 KB Output is correct
16 Correct 8 ms 9984 KB Output is correct
17 Correct 7 ms 9984 KB Output is correct
18 Correct 9 ms 9984 KB Output is correct
19 Correct 7 ms 9984 KB Output is correct
20 Correct 9 ms 9984 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 104 ms 24824 KB Output is correct
6 Correct 60 ms 32376 KB Output is correct
7 Correct 110 ms 29820 KB Output is correct
8 Correct 72 ms 24440 KB Output is correct
9 Correct 105 ms 28180 KB Output is correct
10 Correct 70 ms 24312 KB Output is correct
11 Correct 6 ms 9728 KB Output is correct
12 Correct 7 ms 9728 KB Output is correct
13 Correct 7 ms 10016 KB Output is correct
14 Execution timed out 1085 ms 36032 KB Time limit exceeded
15 Halted 0 ms 0 KB -