Submission #658573

#	Time	Username	Problem	Language	Result	Execution time	Memory
658573		Richem	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	506 ms	49828 KiB

diameter

#include <iostream>
#include <vector>
#include <map>
#define int long long

using namespace std;

const int MAX_SOMMET = 1e5+42, MAX_FEUILLE = (1 << 18), INF = 1e16;

int nbSommet, nbReq, limitePoids;

int ab[MAX_FEUILLE*2][5] = {0};
int aAdd[MAX_FEUILLE*2] = {0};

void unir(int id) {
    ab[id][0] = max(ab[id*2][0], ab[id*2+1][0]);
    ab[id][1] = min(ab[id*2][1], ab[id*2+1][1]);
    ab[id][2] = max(max(ab[id*2][2], ab[id*2+1][2]), ab[id*2][0] - 2 * ab[id*2+1][1]);
    ab[id][3] = max(max(ab[id*2][3], ab[id*2+1][3]), ab[id*2+1][0] - 2 * ab[id*2][1]);
    ab[id][4] = max(max(ab[id*2][4], ab[id*2+1][4]), max(ab[id*2][2] + ab[id*2+1][0], ab[id*2][0] + ab[id*2+1][3]));
}

void applyOp(int id, int add) {
    for(int type = 0; type < 4; type++) {
        ab[id][type] += add;
        if(type >= 2) 
            ab[id][type] -= (add * 2);
    }
    aAdd[id] += add;
}

int applyReq(int deb, int fin, int debReq, int finReq, int id, int val) {
    if(deb > finReq || fin < debReq) 
        return 0;

    if(debReq <= deb && fin <= finReq) {
        applyOp(id, val);
        return 0;
    }

    applyOp(id*2, aAdd[id]);
    applyOp(id*2+1, aAdd[id]);
    aAdd[id] = 0;

    int milieu = (deb + fin+1) / 2;

    applyReq(deb, milieu-1, debReq, finReq, id*2, val);
    applyReq(milieu, fin, debReq, finReq, id*2+1, val);

    unir(id);

    return ab[id][4];
}

int interTemps[MAX_SOMMET][2];

vector<pair<int, int>> adj[MAX_SOMMET];

int prof[MAX_SOMMET] = {0};

vector<int> eulerTour;

void dfs(int sommet, int pere) {
    interTemps[sommet][0] = eulerTour.size();
    eulerTour.push_back(sommet);

    for(auto voisin : adj[sommet]) {
        if(voisin.first == pere)
            continue;

        prof[voisin.first] = prof[sommet] + voisin.second;
        dfs(voisin.first, sommet);
        eulerTour.push_back(sommet);
    }

    interTemps[sommet][1] = eulerTour.size()-1;
}

struct Arete{
    int deb, fin, cost;
};

Arete listeArete[MAX_SOMMET];

void input() {
    cin >> nbSommet >> nbReq >> limitePoids;

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

        adj[--u].push_back({--v, c});
        adj[v].push_back({u, c});

        listeArete[arete] = {u, v, c};
    }
}

int last = 0;

int calcReq(int d, int e) {
    Arete qui = listeArete[(d + last) % (nbSommet-1)];
    int poidsNouv = (e + last) % limitePoids;

    int u = qui.deb, v = qui.fin;

    if(interTemps[u][0] < interTemps[v][0])
        swap(u, v);

    int rep = applyReq(0, MAX_FEUILLE-1, interTemps[u][0], interTemps[u][1], 1, poidsNouv - qui.cost);
    listeArete[(d + last) % (nbSommet-1)] = {u, v, poidsNouv};

    last = rep;


    return rep;
}

void printAb() {
    for(int i = 1; i < MAX_FEUILLE*2; i++) {
        cout << i << " ";
        for(int j = 0; j < 5; j++) {
            cout << ab[i][j] << " ";
        }
        cout << endl;
    }
}

signed main() {
    input();
    dfs(0, -1);

    for(int i = 0; i < MAX_FEUILLE*2; i++) {
        for(int j = 0; j < 5; j++) {
            ab[i][j] = -INF;
            if(j == 1)
                ab[i][j] = INF;
        }
    }

    for(int id = 0; id < eulerTour.size(); id++) {
        int posAb = id + MAX_FEUILLE;

        ab[posAb][0] = ab[posAb][1] = prof[eulerTour[id]];
        ab[posAb][2] = ab[posAb][3] = -prof[eulerTour[id]];
    }

    for(int noeud = MAX_FEUILLE-1; noeud > 0; noeud--) {
        unir(noeud);
    }

    for(int req = 0; req < nbReq; req++) {
        int d,e;
        cin >> d >> e;

        cout << calcReq(d, e) << "\n";
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:143:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int id = 0; id < eulerTour.size(); id++) {
      |                     ~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27