Submission #709216

#	Time	Username	Problem	Language	Result	Execution time	Memory
709216		Dan4Life	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	87 ms	12016 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN = (int)1e5+10;
const int LINF = (int)1e18;
int n, m, x, y;
vector<int> adj[mxN];
int node[mxN], dp[mxN];

struct road{ int a, b, c; };
road v[mxN];

bool dfs(int s, int t, int v, int p){
    if(s==t) return true;
    for(auto u : adj[s]){
        if(u==p) continue;
        if(dfs(u,t,v,s)){ node[u]+=v; return 1; }
    }
    return 0;
}

void add(int s, int t, int v){
    // this can be done in O(logN) or O(1) with sparse tables...
    node[s]+=v; dfs(s,t,v,-1);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n; int ans = 0;
    for(int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        adj[x].pb(y), adj[y].pb(x);
    }
    cin >> m;
    vector<int> xd; xd.pb(0);
    for(int i = 0; i < m; i++){
        cin >> v[i].a >> v[i].b >> v[i].c;
        if(v[i].a>v[i].b) swap(v[i].a,v[i].b); 
        xd.pb(v[i].b);//, xd.pb(v[i].b);
    }
    sort(v,v+m,[&](road x, road y){ return x.b<y.b; });
    sort(all(xd));
    for(int i = 0; i < m; i++){
        int a = v[i].a, b = v[i].b, c = v[i].c;
        int pr = xd[lower_bound(all(xd),v[i].a)-begin(xd)-1];
        int pr2 = xd[lower_bound(all(xd),v[i].b)-begin(xd)-1];
        dp[b] = max({dp[b],dp[pr2],dp[pr]+c});
        ans = max(ans, dp[b]);
    }
    cout << ans;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int32_t main()':
election_campaign.cpp:50:13: warning: unused variable 'a' [-Wunused-variable]
   50 |         int a = v[i].a, b = v[i].b, c = v[i].c;
      |             ^

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