oj.uz

Submission #709215

# Submission time Handle Problem Language Result Execution time Memory
709215 2023-03-13T08:31:22 Z Dan4Life Election Campaign (JOI15_election_campaign) C++17
0 / 100
 90 ms 10184 KB 
#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[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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 10184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 40.0

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