Submission #248943

#	Time	Username	Problem	Language	Result	Execution time	Memory
248943		Richem	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	359 ms	31480 KiB

election_campaign

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

const int MAX_NB = 1e5, MAX_PUISSANCE = 19, INFINI = -1e9;

int nbSommet, nbChemin;
int nbFeuille;

vector<int> adj[MAX_NB];

void input() {
    cin >> nbSommet;

    nbFeuille = (1 << ((int)ceil(log2(nbSommet*2))));

    for(int arete = 0; arete < nbSommet-1; arete++) {
        int u,v;
        cin >> u >> v;
        u--; v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

int bl[MAX_NB][MAX_PUISSANCE];
int temps[MAX_NB][2];
int tempsDfs = 0;

int dfs(int sommet, int preced) {
    bl[sommet][0] = preced;
    for(int exp = 1; exp < MAX_PUISSANCE; exp++) {
        bl[sommet][exp] = -1;
        if(bl[sommet][exp-1] != -1) {
            bl[sommet][exp] = bl[bl[sommet][exp-1]][exp-1];
        }
    }

    temps[sommet][0] = tempsDfs++;

    for(auto fils : adj[sommet]) {
        if(fils != preced) {
            dfs(fils, sommet);
        }
    }

    temps[sommet][1] = tempsDfs++;
}

bool pere(int u, int v) {
    return (temps[u][0] <= temps[v][0] && temps[u][1] >= temps[v][1]);
}

int lca(int u, int v) {
    if(pere(u, v))
        return u;
    if(pere(v, u))
        return v;
    for(int exp = MAX_PUISSANCE-1; exp >= 0; exp--) {
        if(bl[u][exp] != -1 && !pere(bl[u][exp], v)) {
            u = bl[u][exp];
        }
    }

    return bl[u][0];
}

int arbre[(1 << MAX_PUISSANCE)] = {0};


void modif(int idSommet, int valeur) {
    int id[2] = {temps[idSommet][0]+nbFeuille, temps[idSommet][1]+nbFeuille};
    int nombre[2] = {valeur, -valeur};

    for(int i = 0; i < 2; i++) {
        arbre[id[i]] = nombre[i];
        id[i] /= 2;
        for(; id[i] > 0; id[i] /= 2) {
            arbre[id[i]] = arbre[id[i]*2] + arbre[id[i]*2+1];
        }
    }
}

int somme(int debut, int fin) {
    int total = 0, requete[2][2] = {{temps[lca(debut, fin)][0], temps[debut][0]}, {temps[lca(debut, fin)][0], temps[fin][0]}};

    for(int i = 0; i < 2; i++) {
        int gauche = requete[i][0]+nbFeuille, droite = requete[i][1]+nbFeuille;

        while(gauche <= droite) {
            if(gauche%2==1) {
                total += arbre[gauche];
                gauche++;
            }
            if(droite % 2 == 0) {
                total += arbre[droite];
                droite--;
            }
            gauche /= 2; droite /= 2;
        }
    }

    return total;
}

struct Chemin{
    int u, v, nombre;
};

vector<Chemin> chemin[MAX_NB];

void inputChemin() {
    cin >> nbChemin;

    for(int i = 0; i < nbChemin; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        chemin[lca(a, b)].push_back({a, b, c});
    }
}

int dp[MAX_NB][2];

void calculerDp(int sommet, int preced) {
    if(dp[sommet][0] != INFINI)
        return;

    dp[sommet][0] = 0;

    for(auto fils : adj[sommet]) {
        if(fils != preced) {
            calculerDp(fils, sommet);
            dp[sommet][0] += dp[fils][1];
        }
    }

    dp[sommet][1] = dp[sommet][0];

    for(auto path : chemin[sommet]) {
        dp[sommet][1] = max(dp[sommet][1], dp[sommet][0] + path.nombre + somme(sommet, path.u) + somme(sommet, path.v) - 2 * somme(sommet, sommet));
    }

    modif(sommet, dp[sommet][0] - dp[sommet][1]);
}

int main() {

    for(int i = 0; i < MAX_NB; i++) dp[i][0] = dp[i][1] = INFINI;

    input();
    dfs(0, -1);
    inputChemin();

    calculerDp(0, -1);

    cout << max(dp[0][0], dp[0][1]);
}

Compilation message (stderr)

election_campaign.cpp: In function 'int dfs(int, int)':
election_campaign.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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