Submission #373367

#	Time	Username	Problem	Language	Result	Execution time	Memory
373367		BartolM	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	246 ms	32644 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int LOG=17;
const int N=1e5+5;

int n, q, dtime=1;
int L[N], R[N];
int par[LOG][N], dep[N];
vector <ppi> v[N];
vector <int> ls[N];
ll dp[N], F[2*N];

ll query(int x) {
    ll ret=0;
    for (; x>0; x-=x&-x) ret+=F[x];
    return ret;
}

void update(int x, ll val) {
    for (; x<=2*n; x+=x&-x) F[x]+=val;
}

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=1; j<=n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

int digni(int x, int d) {
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=d) x=par[i][x];
    }
    return x;
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    x=digni(x, dep[y]);
    if (x==y) return x;
    for (int i=LOG-1; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

void dfs(int node, int rod) {
    dep[node]=dep[rod]+1;
    L[node]=dtime++;
    par[0][node]=rod;
    for (int sus:ls[node]) if (sus!=rod) dfs(sus, node);
    R[node]=dtime++;
}

ll rek(int node) {
    ll sum=0, ret=0;
    for (int sus:ls[node]) {
        if (sus==par[0][node]) continue;
        ret=max(ret, rek(sus));
        sum+=dp[sus];
    }
    dp[node]=sum;
    for (ppi pp:v[node]) {
        ll curr=sum+pp.Y;
        if (pp.X.X!=node) curr+=query(L[pp.X.X]);
        if (pp.X.Y!=node) curr+=query(L[pp.X.Y]);
        dp[node]=max(dp[node], curr);
    }
    ret=max(ret, dp[node]);
    update(L[node], sum-dp[node]);
    update(R[node], dp[node]-sum);
    return ret;
}


void load() {
    scanf("%d", &n);
    for (int i=0; i<n-1; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        ls[a].pb(b); ls[b].pb(a);
    }
    dfs(1, 0);
    build();
    scanf("%d", &q);
    for (int i=0; i<q; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        int lc=lca(a, b);
        v[lc].pb(mp(mp(a, b), c));
    }
}

int main() {
    load();
    printf("%lld\n", rek(1));
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void load()':
election_campaign.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
election_campaign.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
election_campaign.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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