제출 #1288393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288393		monaxia	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	192 ms	34740 KiB

election_campaign

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
using namespace std;
using namespace __gnu_pbds; 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ull Mod = 1e9 + 7;
constexpr ull sqr = 223;
constexpr ld eps = 1e-9;
constexpr int N = 1e5;
int n;
ll st[4 * N + 5];
void update111(int idx, int l, int r, int i, ll val){
    if(l == r){
        st[idx] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(i <= mid) update111(idx << 1, l, mid, i, val);
    else update111(idx << 1 | 1, mid + 1, r, i, val);
    st[idx] = st[idx << 1] + st[idx << 1 | 1];
}
ll query111(int idx, int l, int r, int u, int v){
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[idx];
    int mid = (l + r) >> 1;
    return query111(idx << 1, l, mid, u, v) + query111(idx << 1 | 1, mid + 1, r, u, v);
}
void update(int i, ll val){ update111(1, 1, N, i, val); }
ll query(int l, int r){ return query111(1, 1, N, l, r); }
vector <int> graph[N + 5];
int h[N + 5], subtr[N + 5], p[N + 5][25];
int heavy_p[N + 5];
int id[N + 5];
int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int diff = h[u] - h[v];
    for(int i = 20; i >= 0; i--){
        if(diff & (1 << i)){
            u = p[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 20; i >= 0; i--){
        if(p[u][i] != p[v][i]){
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}
void dfs111(int node, int pr){
    h[node] = h[pr] + 1;
    subtr[node] = 1;
    p[node][0] = pr;
    for(int i = 1; i <= 20; i++){
        p[node][i] = p[p[node][i-1]][i-1];
    }
    for(auto& x : graph[node]){
        if(x == pr) continue;
        dfs111(x, node);
        subtr[node] += subtr[x];
    }
}
int timer = 0;
void dfs222(int node, int pr){
    id[node] = ++ timer;
    pair <int, int> mx = {0, 0};
    for(auto& x : graph[node]){
        if(x == pr) continue;
        mx = max(mx, {subtr[x], x});
    }
    if(mx.fr){
        heavy_p[mx.sc] = heavy_p[node];
        dfs222(mx.sc, node);
    }
    for(auto& x : graph[node]){
        if(x == mx.sc || x == pr) continue;
        heavy_p[x] = x;
        dfs222(x, node);
    }
}
void preprocess(){
    memset(st, 0, sizeof(st));
    for(int i = 0; i <= n; ++i) for(int j = 0; j < 25; ++j) p[i][j] = 0;
    heavy_p[1] = 1;
    dfs111(1, 0);
    dfs222(1, 0);
}
void update1(int u, ll val){
    update(id[u], val);
}
ll query_subpath_excluding_anc(int u, int anc){
    ll ans = 0;
    while(heavy_p[u] != heavy_p[anc]){
        ans += query(id[heavy_p[u]], id[u]);
        u = p[heavy_p[u]][0];
    }
    if(id[anc] + 1 <= id[u]) ans += query(id[anc] + 1, id[u]);
    return ans;
}
ll query1(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int pr = lca(u, v);
    ll ans = 0;
    ans += query_subpath_excluding_anc(u, pr);
    ans += query_subpath_excluding_anc(v, pr);
    return ans;
}
struct eded{
    int fr, sc;
    ll val;
};
vector <eded> ed[N + 1];
ll base[N + 1], dp[N + 1];

void dfs(int node, int pr){
    base[node] = 0;
    for(auto& x : graph[node]) if(x != pr){
        dfs(x, node);
        base[node] += dp[x];
    }
    ll mx = 0;
    for(auto& w : ed[node]){
        ll s = query1(w.fr, w.sc);
        ll cand = w.val - s;
        if(cand > mx) mx = cand;
    }
    if(mx < 0) mx = 0;
    dp[node] = base[node] + mx;
    update1(node, mx);
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    preprocess();
    int m;
    cin >> m;
    for(int i = 1; i <= m; i ++){
        int u, v;
        ll val;
        cin >> u >> v >> val;
        int pr = lca(u, v);
        ed[pr].pb({u, v, val});
    }
    dfs(1, 0);
    cout << dp[1];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    if(fopen("nameholder.inp", "r")){
        freopen("nameholder.inp", "r", stdin);
        freopen("nameholder.out", "w", stdout);
    }
    int t = 1;
    while(t --){
        solve();
        cout << "\n";
    }
    cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}
// Whose eyes are those eyes?

컴파일 시 표준 에러 (stderr) 메시지

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen("nameholder.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen("nameholder.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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