제출 #1288088

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

election_campaign

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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;

int n, m;
vector <int> graph[100005];
int h[100005], p[100005][20];

void dfs1(int node, int pr){
    p[node][0] = pr;
    h[node] = h[pr] + 1;

    for(int i = 1; i <= __lg(n); i ++) if(p[node][i - 1] != - 1) p[node][i] = p[p[node][i - 1]][i - 1];

    for(auto& x : graph[node]) if(x != pr) dfs1(x, node); 
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);

    while(h[u] > h[v]) u = p[u][__lg(h[u] - h[v])];

    for(int i = __lg(n); i >= 0; i --) if(p[u][i] != p[v][i]){
        u = p[u][i];
        v = p[v][i];
    }

    while(u != v){
        u = p[u][0];
        v = p[v][0];
        break;
    }

    return u;
}

vector <int> ed1[100005];
int top[100005], val[100005], dp[100005];
pair <int, int> sss[100005];

int childof(int u, int pr){
    while(h[u] > h[pr] + 1){
        u = p[u][__lg(h[u] - h[pr] - 1)];
    }

    return u;
}

void dfs(int node, int pr){
    multiset <int> ans;

    ans.insert(0);
    ans.insert(0);
    ans.insert(0);

    for(auto& x : graph[node]){
        if(x == pr) continue;
        dfs(x, node);

        ans.insert(dp[x]);

        dp[node] = max(dp[node], dp[x]);
    }

    for(auto& x : ed1[node]) {
        if(top[x] == node){
            int xx = childof(sss[x].fr, node), y = - 1;
            auto it = ans.find(dp[xx]);
            if(it != ans.end()) ans.erase(it);

            if(sss[x].sc != node){
                y = childof(sss[x].sc, node);
                it = ans.find(dp[y]);
                if(it != ans.end()) ans.erase(it);
            }

            val[x] += *ans.rbegin();

            if(it != ans.end()) ans.insert(dp[xx]);
            if(y != -1) ans.insert(dp[y]);
        }

        else val[x] += *ans.rbegin();

        dp[top[x]] = max(dp[top[x]], val[x]);
    }

    // cout << node << " " << dp[node] << "\n";
}

void solve(){
    memset(p, -1, sizeof(p));
    memset(top, 0, sizeof(top));
    memset(dp, 0, sizeof(dp));

    cin >> n;

    for(int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        graph[u].pb(v);
        graph[v].pb(u);
    }

    dfs1(1, 0);

    int timer = 0;

    cin >> m;

    while(m --){
        int u, v, vl;
        cin >> u >> v >> vl;

        timer ++;

        if(h[u] < h[v]) swap(u, v);

        sss[timer] = {u, v};

        val[timer] = vl;
        top[timer] = lca(u, v);

        dp[top[timer]] = max(dp[top[timer]], vl);

        ed1[u].pb(timer);
        ed1[v].pb(timer);
        if(v != top[timer]) ed1[top[timer]].pb(timer);
    }

    // for(int i = 1; i <= n; i ++) cout << top[i] << ' '; return;

    dfs(1, 0);

    cout << dp[1]; 

    // for(int i = 1; i <= n; i ++){
    //     for(auto& x : ed1[i]) cout << x << " "; cout << "\n";
    // }
}

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;

    // cin >> t;

    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: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.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen("nameholder.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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