Submission #709216

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
709216	2023-03-13T08:32:02 Z	Dan4Life	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	87 ms	12016 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Incorrect	1 ms	2644 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	71 ms	11728 KB	Output is correct
5	Correct	72 ms	11760 KB	Output is correct
6	Correct	67 ms	11764 KB	Output is correct
7	Correct	77 ms	11648 KB	Output is correct
8	Correct	75 ms	11644 KB	Output is correct
9	Correct	67 ms	11652 KB	Output is correct
10	Correct	70 ms	11644 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	71 ms	11728 KB	Output is correct
5	Correct	72 ms	11760 KB	Output is correct
6	Correct	67 ms	11764 KB	Output is correct
7	Correct	77 ms	11648 KB	Output is correct
8	Correct	75 ms	11644 KB	Output is correct
9	Correct	67 ms	11652 KB	Output is correct
10	Correct	70 ms	11644 KB	Output is correct
11	Correct	12 ms	3800 KB	Output is correct
12	Correct	75 ms	12012 KB	Output is correct
13	Correct	75 ms	11984 KB	Output is correct
14	Correct	73 ms	12016 KB	Output is correct
15	Correct	77 ms	11928 KB	Output is correct
16	Correct	74 ms	11932 KB	Output is correct
17	Correct	76 ms	12004 KB	Output is correct
18	Correct	79 ms	12016 KB	Output is correct
19	Correct	74 ms	11924 KB	Output is correct
20	Correct	87 ms	11976 KB	Output is correct