답안 #709216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709216 2023-03-13T08:32:02 Z Dan4Life Election Campaign (JOI15_election_campaign) C++17
10 / 100
87 ms 12016 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[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;
      |             ^
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 10008 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -