Submission #1283916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283916		vuquangsang	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	131 ms	28472 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define     el "\n"
#define     FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define     FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define     pb push_back
#define     fi first
#define     se second
#define     all(x) x.begin(),x.end()
#define     lg(x) __lg(x)
#define     alla(a,n) a+1,a+n+1
#define     ll long long
#define     pii pair<int, int>


template <class T> bool maxi(T &x, T y) { if(x < y) { x = y ; return true ;} return false;}
template <class T> bool mini(T &x, T y) { if(x > y) { x = y ; return true ;} return false;}

const int N = 1e5 + 2;

int n, q;
vector<int> adj[N];
struct Queries
{
    int x, y, w;
} queries[N];

vector<int> qry[N];

int timer = 0, tin[N], tout[N];
int h[N], up[N][21];
void dfs(int u, int p )
{
    tin[u] = ++timer;

    up[u][0] = p;
    for(int j = 1; j <= lg(n); j++) up[u][j] = up[up[u][j - 1]][j - 1];

    for(int v : adj[u]) if(v != p) {
        h[v] = h[u] + 1;
        dfs(v, u);
    }

    tout[u] = timer;
}

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

    FORD(j, lg(n), 0) if(h[up[u][j]] >= h[v]) u = up[u][j];
    if(u == v) return u;
    FORD(j, lg(n), 0) if(up[u][j] != up[v][j]) {
        u = up[u][j];
        v = up[v][j];
    }
    return up[u][0];
}

long long dp[N], dpChild[N];

long long bit[N];

void upd(int x, ll v)
{
    for(; x <= n; x += x & -x) bit[x] += v;
}
long long get(int x)
{
    ll ans = 0;
    for(; x >= 1; x -= x & -x) ans += bit[x];
    return ans;
}
void update(int l, int r, ll v)
{
    upd(l, v);
    upd(r + 1, -v);
}

long long getPath(int u, int v)
{
    return get(tin[u]) + get(tin[v]);
}
void dfsAns(int u, int p)
{
    for(int v : adj[u]) if(v != p) {
        dfsAns(v, u);
        dpChild[u] += dp[v];
    }
    dp[u] = dpChild[u];

    for(int idx : qry[u]) {
        // u is lca
        int x = queries[idx].x, y = queries[idx].y, w = queries[idx].w;
        dp[u] = max(dp[u], dpChild[u] + getPath(x, y) + w);
    }

    update(tin[u], tout[u], dpChild[u] - dp[u]);
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define __Azul__ ""
    if(fopen(__Azul__".inp", "r")) {
        freopen(__Azul__".inp", "r", stdin);
        freopen(__Azul__".out", "w", stdout);
    }

    cin >> n;
    for(int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs(1, 1);

    cin >> q;
    for(int i = 1; i <= q; i++) {
        int x, y, w; cin >> x >> y >> w;
        queries[i] = {x, y, w};

        qry[LCA(x, y)].push_back(i);
    }

    dfsAns(1, 1);

    cout << dp[1];

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

Compilation message (stderr)

election_campaign.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main()
      | ^~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(__Azul__".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(__Azul__".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