Submission #1106273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106273		attky	Nile (IOI24_nile)	C++17	100 / 100	118 ms	39356 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#define int long long 

using namespace std;

const int INF = 2e17;
const int MAX = 1e5+42;

struct Requ {
    int requete, id;

    bool operator< (Requ other) {
        return requete < other.requete;
    }
};

struct Comp {
    int pere, cout, minPair, minImpair, minSaut, taille, iPremier;

    bool operator< (Comp other) {
        return taille < other.taille;
    }
};

struct Dist {
    int ecart, id, type;

    bool operator< (Dist other) {
        return ecart < other.ecart;
    }
};

struct Reli {
    int poids, coutSeul, coutDeux, diffCout;

    bool operator< (Reli other) {
        return poids < other.poids;
    }
};

vector<Reli> relique;
vector<Requ> requete;
vector<Comp> composante(MAX);
vector<Dist> dist;
vector<int> answer;
vector<int> fils[MAX];
int sommeTotal = 0;


void merge(Dist arete) {
    int nodeA = composante[arete.id].pere;
    int nodeB = composante[arete.id + 1].pere;

    if(composante[nodeA] < composante[nodeB]) {
        swap(nodeA, nodeB);
    }
    for(int loop = 0; loop < fils[nodeB].size(); ++loop) {
        composante[fils[nodeB][loop]].pere = nodeA;
        fils[nodeA].push_back(fils[nodeB][loop]);
    }
    composante[nodeA].taille = fils[nodeA].size();
    composante[nodeB].taille = 0;
    fils[nodeB].clear();
    composante[nodeA].iPremier = min(composante[nodeA].iPremier, composante[nodeB].iPremier);
    composante[nodeA].minImpair = min(composante[nodeA].minImpair, composante[nodeB].minImpair);
    composante[nodeA].minPair = min(composante[nodeA].minPair, composante[nodeB].minPair);
    composante[nodeA].minSaut = min(composante[nodeA].minSaut, composante[nodeB].minSaut);

    sommeTotal -= composante[nodeA].cout + composante[nodeB].cout;
    if(composante[nodeA].taille % 2 == 0) {
        composante[nodeA].cout = 0;
    }
    else {
        int coutMin = composante[nodeA].minSaut;
        if(composante[nodeA].iPremier % 2 == 0) {
            composante[nodeA].cout = min(coutMin, composante[nodeA].minPair);
        }
        else {
            composante[nodeA].cout = min(coutMin, composante[nodeA].minImpair);
        }
    }
    sommeTotal += composante[nodeA].cout;
}

void update(Dist arete) {
    int node = composante[arete.id].pere;
    composante[node].minSaut = min(composante[node].minSaut, relique[arete.id].diffCout);

    sommeTotal -= composante[node].cout;
    composante[node].cout = min(composante[node].cout, composante[node].minSaut);
    sommeTotal += composante[node].cout;
}

#undef int long long 
vector<long long> calculate_costs(vector<int> poids, vector<int> coutSeul, vector<int> coutDeux, vector<int> E) {
    int n = poids.size();

    for(int loop = 0; loop < n; ++loop) {
        relique.push_back({poids[loop], coutSeul[loop], coutDeux[loop], coutSeul[loop] - coutDeux[loop]});        
    }
    sort(relique.begin(), relique.end());

    int q = E.size();
    for(int loop = 0; loop < q; ++loop) {
        answer.push_back(0);
        requete.push_back({0, 0});
    }
    for(int loop = 0; loop < q; ++loop) {
        requete[loop] = {E[loop], loop};
    }
    sort(requete.begin(), requete.end());

    for(int loop = 0; loop < n; ++loop) {
        composante[loop].pere = loop;
        composante[loop].cout = relique[loop].diffCout;
        composante[loop].minSaut = INF;
        composante[loop].taille = 1;
        composante[loop].iPremier = loop;
        if(loop % 2 == 0) {
            composante[loop].minPair = relique[loop].diffCout;
            composante[loop].minImpair = INF;
        }
        else {
            composante[loop].minPair = INF;
            composante[loop].minImpair = relique[loop].diffCout;
        }
    }

    for(int loop = 0; loop < n-1; ++loop) {
        dist.push_back({relique[loop+1].poids - relique[loop].poids, loop, 1});
    }
    for(int loop = 0; loop < n-2; ++loop) {
        dist.push_back({relique[loop+2].poids - relique[loop].poids, loop+1, 2});
    }
    dist.push_back({INF, -1, -1});
    sort(dist.begin(), dist.end());

    for(int loop = 0; loop < n; ++loop) {
        fils[loop].push_back(loop);
    }

    for(int loop = 0; loop < n; ++loop) {
        sommeTotal += relique[loop].coutSeul;
    }
    int iEcart = 0;
    for(int loop = 0; loop < q; ++loop) {
        while(dist[iEcart].ecart <= requete[loop].requete) {
            if(dist[iEcart].type == 1) {
                merge(dist[iEcart]);
            }
            else {
                update(dist[iEcart]);
            }
            iEcart++;
        }
        answer[requete[loop].id] = sommeTotal;
    }
    return answer;
}

Compilation message (stderr)

nile.cpp:95:12: warning: extra tokens at end of #undef directive
   95 | #undef int long long
      |            ^~~~
nile.cpp: In function 'void merge(Dist)':
nile.cpp:58:28: 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]
   58 |     for(int loop = 0; loop < fils[nodeB].size(); ++loop) {
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18