Submission #1238846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238846		YassirSalama	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	99 ms	42152 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
using ull=unsigned long long;
using pii=pair<int,int>;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
    copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int maxn = 1e5+100;
const int logn = 20;
vector<int> v[maxn];
int up[maxn][logn];
int depth[maxn];
void dfs(int node,int par){
    depth[node] = depth[par]+1;
    up[node][0] = par;
    for(int i=1;i<logn;i++){
        up[node][i] = up[up[node][i-1]][i-1];
    }
    for(auto x : v[node]){
        if(x==par) continue;
        dfs(x,node);
    }
}
int LCA(int a,int b){
    if(depth[a]<depth[b]) swap(a,b); 
    int d = depth[a]-depth[b];
    for(int i=0;i<logn;i++){
        if((1LL<<i)&d){
            a = up[a][i];
        }
    }
    if(a==b) return a;
    for(int i = logn-1;i>=0;i--){
        if(up[a][i]==up[b][i]) continue;
        a = up[a][i];
        b = up[b][i];
    }
    return up[a][0];
}
vector<vector<int>> queries[maxn];
int goup(int a,int k){
    for(int i = 0;i<logn;i++){
        if((1LL<<i)&k){
            a = up[a][i];
        }
    }
    return a;
}
int dp[maxn];
int ans = 0;
int dp2[maxn];
void dfs2(int node,int par){
    for(auto x : v[node]){
        if(x==par) continue;
        dfs2(x,node);
    }
    int s = 0;
    for(auto x : v[node]){
        if(x==par) continue;
        s+=dp[x];
        dp[node] = max(dp[node],dp[x]);
    }
    dp2[node] = s;
    dp[node] = s;
    int ans = 0;
    for(auto t : queries[node]){
        int a = t[0], b = t[1] , c = t[2];
        int d1 = depth[a]-depth[node] -1;
        int d2 = depth[b] - depth[node]-1;
        if(a==node){
            //then a is LCA is node itself
            int x = goup(b,d2);
            int t = s-dp[x];
            ans = max(ans,c+dp2[b]+t);
        }else if(b==node){
            int x = goup(a,d1);
            int t = s - dp[x];
            ans = max(ans,c+dp2[a]+t);
        }else{
            int x = goup(a,d1);
            int y = goup(b,d2);
            int t = s-dp[x]-dp[y];
            ans = max(ans,dp2[a]+dp2[b]+t+c);
        }
    }
    dbg(node,ans)
    dp[node] = max(ans,dp[node]);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(1,1);
    int m;
    cin>>m;
    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        int l  = LCA(a,b);
        queries[l].pb({a,b,c});
    }
    dfs2(1,1);
    int ans = *max_element(dp+1,dp+n+1);
    cout<<ans<<endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40