Submission #1354567

#TimeUsernameProblemLanguageResultExecution timeMemory
1354567luvwinterElection Campaign (JOI15_election_campaign)C++20
10 / 100
87 ms37016 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
#define fi first
#define se second
#define FOR(i , l , r) for(int i = (l) ; i <= (r) ; i++)
#define FOD(i , r , l) for(int i = (r) ; i >= (l) ; i--)
#define pb push_back
#define endl '\n'
const int N = 2e5 + 5;
const int LOG = 22;

int n;
struct node{
    int x , y , cost;
};
vector<int> adj[N];
int h[N];
int parent[N][LOG];
vector<node> opt[N];
vector<int> order;
int dp[N][2];


void dfs(int u , int p) {
     for(auto v : adj[u]) {
         if(v == parent[u][0]) continue;
         h[v] = h[u] + 1;
         parent[v][0] = u;
         FOR(i , 1 , LOG - 1) {
             parent[v][i] = parent[parent[v][i - 1]][i - 1];
         }
         dfs(v , u);
     }
}
int lca(int u , int v) {
    if(h[u] != h[v]) {
        if(h[u] < h[v]) swap(u, v);
        int k = h[u] - h[v];
        FOR(i , 0 , LOG - 1) {
            if(k >> i & 1LL) {
                u = parent[u][i];
            }
        }
    }
    if(u == v) return u;
    FOD(i , LOG - 1 , 0) {
        if(parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}
int jump(int u , int height) {
    FOR(i , 0 , LOG - 1) {
         if(height >> i & 1) {
            u = parent[u][i];
         }
    }
    return u;
}

bool cmp(const int& a , const int & b) {
     return h[a] > h[b];
}

void solve(void) {
      cin >> n;
      FOR(i , 1 , n - 1) {
          int x , y; cin >> x >> y;
          adj[x].pb(y);
          adj[y].pb(x);
      }
      dfs(1 , 0);

      int m; cin >> m;

      FOR(i , 1 , m) {
          int x , y , cost;
          cin >> x >> y >> cost;
          int p = lca(x , y);
          opt[p].pb({x , y , cost});
      }


      FOR(i , 1 , n) order.push_back(i);
      sort(order.begin() , order.end() , cmp);
      FOR(i , 0 , order.size() - 1) {

           int u = order[i];
           for(auto v : adj[u]) {
               if(v == parent[u][0]) continue;
               dp[u][0] += max(dp[v][0] , dp[v][1]);
           }
           for(auto op : opt[u]) {
               int x = op.x;
               int y = op.y;
               int cost = op.cost;
               int k1 = max(h[x] - h[u] - 1LL , 0LL);
               int k2 = max(h[y] - h[u] - 1LL , 0LL);
               int v1 = jump(x , k1);
               int v2 = jump(y , k2);
               int sum = dp[u][0] - (v1 != u ? max(dp[v1][0] , dp[v1][1]) - dp[x][0] : 0)  - (v2 != u ? max(dp[v2][0] , dp[v2][1]) - dp[y][0] : 0) + cost;

               dp[u][1] = max(dp[u][1] , sum);
               //if(u == 5) cout << "debug : " << v1 << " " << v2 << " " << x << " " << y << " "  << cost << dp[x] << endl;

           }
          // if(u == 5) cout << "debug : " << dp[u][0] << " " << dp[u][1] << endl;

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

}

main () {
    ios_base :: sync_with_stdio(false);
    solve();




    return 0;

}

Compilation message (stderr)

election_campaign.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  118 | main () {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...