Submission #109682

#	Time	Username	Problem	Language	Result	Execution time	Memory
109682		hugo_pm	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	728 ms	39264 KiB

election_campaign

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

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

// Version classique du segment tree
// Opérations en O(log N)
// Indices 0-indexés

class SegtreeClassic
{
    public:
        void init(vector<int> tab);
        int requete(int gauche, int droite);
        void modifier(int index, int val);

    private:
        const int UNDEF = BIG+10;
        int nbElements;
        int combiner(int a, int b);
        vector<int> interne;
};

void SegtreeClassic::init(vector<int> tab)
{
    nbElements = tab.size();
    interne.resize(2 * nbElements);

    for (int ind = 0; ind < nbElements; ++ind)
        interne[ind + nbElements] = tab[ind];

    for (int ind = nbElements - 1; ind >= 0; --ind)
        interne[ind] = combiner(interne[2*ind], interne[2*ind + 1]);
}

int SegtreeClassic::requete(int gauche, int droite)
{
    int res = UNDEF;
    ++droite; // Pour passer à un intervalle semi-ouvert [l ; r[
    gauche += nbElements;
    droite += nbElements;

    while (gauche < droite)
    {
        // Si gauche est impair, le noeud est inclus mais pas le parent
        // On ajoute donc ce noeud et on passera plus tard au noeud à droite du parent
        if (gauche & 1)
            res = combiner(res, interne[gauche++]);
        // Même raisonnement sachant que droite est exclus, d'où la {pré}-décrémentation
        if (droite & 1)
            res = combiner(res, interne[--droite]);
        
        gauche /= 2;
        droite /= 2;
    }

    return res;
}

void SegtreeClassic::modifier(int index, int val)
{
    index += nbElements;
    interne[index] = val;
    index /= 2;
    while (index > 0)
    {
        interne[index] = combiner(interne[2*index], interne[2*index+1]);
        index /= 2;
    }
}

int SegtreeClassic::combiner(int a, int b)
{
    if (a == UNDEF) return b;
    if (b == UNDEF) return a;
    return a + b;
}

const int borne = 100*1000 + 5;
const int lgb = 19;
int nbNoeuds, nbPlans;
vector<int> adj[borne];
int prof[borne], par[borne];
int anc[lgb][borne];

int deb[borne], fin[borne];
int curTemps = 0;

void dfsInit(int nod)
{
	deb[nod] = curTemps++;
	anc[0][nod] = par[nod];
	form2(i, 1, lgb) {
		int tmp = anc[i-1][nod];
		if (tmp == -1) anc[i][nod] = -1;
		else anc[i][nod] = anc[i-1][tmp];
	}
	for (int vo : adj[nod]) if (vo != par[nod]) {
		prof[vo] = prof[nod] + 1;
		par[vo] = nod;
		dfsInit(vo);
	}
	fin[nod] = curTemps++;
}

int lca(int u, int v)
{
	if (u == v) return u;
	if (prof[u] > prof[v]) swap(u,v); // v devient le plus profond
	ford(i, lgb) {
		int nv = anc[i][v];
		if (nv != -1 && prof[nv] >= prof[u]) {
			v = nv;
		}
	}
	assert(prof[v] == prof[u]);
	if (u == v) return u;
	
	ford(i, lgb) {
		int nu = anc[i][u];
		int nv = anc[i][v];
		if (nu != nv && nu != -1 && nv != -1) {
			u = nu; v = nv;
		}
	}
	assert(u != v);
	assert(par[u] == par[v]);
	return par[u];
}

SegtreeClassic sc;
int somEnf[borne], dp[borne];
typedef pair<pii, int> trio;
vector<trio> splitPlan[borne];

void dfsCalc(int nod)
{
	for (int vo : adj[nod]) if (vo != par[nod]) {
		dfsCalc(vo);
		somEnf[nod] += dp[vo];
	}
	
	dp[nod] = somEnf[nod];

	for (auto plan : splitPlan[nod]) {
		int pushFirst = sc.requete(0, deb[plan.fi.fi]);
		int pushSecond = sc.requete(0, deb[plan.fi.se]);
		chmax(dp[nod], plan.se + pushFirst + pushSecond + somEnf[nod]);
	}

	int valPush = somEnf[nod] - dp[nod];
	sc.modifier(deb[nod], valPush);
	sc.modifier(fin[nod], -valPush);
}

void solve()
{
	cin >> nbNoeuds;
	par[0] = -1;
	form(i, nbNoeuds-1) {
		int u, v; cin >> u >> v;
		--u; --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfsInit(0);
	assert(curTemps == 2*nbNoeuds);
	sc.init(vector<int>(2*nbNoeuds, 0)); 

	cin >> nbPlans;
	form(i, nbPlans) {
		int u, v, rcp; cin >> u >> v >> rcp;
		--u; --v;
		splitPlan[lca(u,v)].push_back({{u,v}, rcp});
	}

	dfsCalc(0);
	cout << dp[0] << "\n";
}

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