Submission #885568

#	Time	Username	Problem	Language	Result	Execution time	Memory
885568		SkillIssueWAGuy	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2201 ms	34756 KiB

potion

#include<vector>
#include<utility>
#include<cmath>
#include<algorithm>
using namespace std;
namespace cj{
    vector<int> h, a, b;
    int n, d, u, sqrtu;
    vector<vector<vector<int>>> big;
    vector<vector<pair<int,int>>> graph;
    vector<vector<vector<pair<int,int>>>> small;
    vector<vector<int>> slots;
    bool Comp(pair<int,int> A, pair<int,int> B){
        if (h[A.first] == h[B.first]){
            return A.first < B.first;
        }
        return h[A.first] < h[B.first];
    }
    bool C(int A, int B){
        if (h[A] == h[B]){
            return A < B;
        }
        return h[A] < h[B];
    }
    bool Comp2(pair<int,int> A, pair<int,int> B){
        return A.second < B.second;
    }
    inline void push(vector<int> &V, int val){
        if (V.empty()){
            V.push_back(val);
        }
        else if (V.back() != val){
            V.push_back(val);
        }
        else {
            V.pop_back();
        }
    }
    template<class _T>
    inline void copy(vector<_T> &from, vector<_T> &to){
        to.clear();
        for (int i : from){
            to.push_back(i);
        }
    }
    inline void clean(vector<int> &V){
        vector<int> p;
        copy<int>(V, p);
        sort(p.begin(), p.end(), C);
        V.clear();
        for (int i : p){
            push(V, i);
        }
        return;
    }
}

void init(int N, int D, int H[]) {
    cj::n = N;
    cj::d = D;
    cj::h = vector<int>(N);
    cj::graph = vector<vector<pair<int,int>>>(cj::n, vector<pair<int,int>>(0));
    cj::big = vector<vector<vector<int>>>(cj::n, vector<vector<int>>(0));
    cj::small = vector<vector<vector<pair<int,int>>>>(cj::n, vector<vector<pair<int,int>>>(0));
    cj::slots = vector<vector<int>>(cj::n, vector<int>(0));
    for (int i = 0; i < N; i++){
        cj::h[i] = H[i];
    }
}

void curseChanges(int U, int A[], int B[]) {
    cj::u = U;
    cj::a = cj::b = vector<int>(U);
    for (int i = 0; i < U; i++){
        cj::a[i] = A[i];
        cj::b[i] = B[i];
    }
    cj::sqrtu = floor(sqrt(cj::u));
    for (int i = 0; i < U; i++){
        cj::graph[cj::a[i]].push_back({cj::b[i], i});
        cj::graph[cj::b[i]].push_back({cj::a[i], i});
    }
    for (int i = 0; i < cj::n; i++){
        sort(cj::graph[i].begin(), cj::graph[i].end(), cj::Comp2);
    }
    for (int i = 0; i < cj::n; i++){
        cj::big[i].push_back({});
        cj::small[i].push_back({});
        cj::slots[i].push_back(0);
        for (int j = 0; j < cj::graph[i].size(); j++){
            if (cj::small[i].size() == cj::sqrtu){
                cj::big[i].push_back({});
                cj::copy<int>(*(cj::big[i].end() - 2), cj::big[i].back());
                for (pair<int,int> p : cj::small[i].back()){
                    cj::big[i].back().push_back(p.first);
                }
                cj::clean(cj::big[i].back());
                cj::small[i].push_back({});
                cj::slots[i].push_back(1e9);
            }
            cj::small[i].back().push_back(cj::graph[i][j]);
            if (cj::slots[i].back() == 1e9){
                cj::slots[i].back() = cj::small[i].back()[0].second;
            }
        }
        for (int j = 0; j < cj::small[i].size(); j++){
            sort(cj::small[i][j].begin(), cj::small[i][j].end(), cj::Comp);
        }
    }
}

inline void genseq(int x, int v, vector<int> &ret){
    int slot;
    vector<int> s;
    ret.clear();
    for (int i = cj::slots[x].size() - 1; i >= 0; i--){
        if (cj::slots[x][i] <= v){
            slot = i;
            break;
        }
    }
    for (pair<int,int> i : cj::small[x][slot]){
        if (i.second <= v){
            cj::push(s, i.first);
        }
    }
    int p1 = 0, p2 = 0;
    while (p1 < s.size() || p2 < cj::big[x][slot].size()){
        if (p1 == s.size()){
            cj::push(ret, cj::big[x][slot][p2]);
            p2++;
        }
        else if (p2 == cj::big[x][slot].size()){
            cj::push(ret, s[p1]);
            p1++;
        }
        else if (cj::h[s[p1]] > cj::h[cj::big[x][slot][p2]]){
            cj::push(ret, cj::big[x][slot][p2]);
            p2++;
        }
        else {
            cj::push(ret, s[p1]);
            p1++;
        }
    }
}

int question(int x, int y, int v) {
    v--;
    if (v == -1) return 1e9;
    vector<int> xseq, yseq;
    genseq(x, v, xseq);
    genseq(y, v, yseq);
    int p1 = 0, p2 = 0, output = 1e9;
    while (p1 < xseq.size() && p2 < yseq.size()){
        output = min(output, abs(cj::h[xseq[p1]] - cj::h[yseq[p2]]));
        if (cj::h[xseq[p1]] < cj::h[yseq[p2]]){
            p1++;
        }
        else {
            p2++;
        }
    }
    return output;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int j = 0; j < cj::graph[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
potion.cpp:91:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |             if (cj::small[i].size() == cj::sqrtu){
      |                 ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
potion.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int j = 0; j < cj::small[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void genseq(int, int, std::vector<int>&)':
potion.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     while (p1 < s.size() || p2 < cj::big[x][slot].size()){
      |            ~~~^~~~~~~~~~
potion.cpp:128:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     while (p1 < s.size() || p2 < cj::big[x][slot].size()){
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp:129:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         if (p1 == s.size()){
      |             ~~~^~~~~~~~~~~
potion.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         else if (p2 == cj::big[x][slot].size()){
      |                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:155:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     while (p1 < xseq.size() && p2 < yseq.size()){
      |            ~~~^~~~~~~~~~~~~
potion.cpp:155:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     while (p1 < xseq.size() && p2 < yseq.size()){
      |                                ~~~^~~~~~~~~~~~~
potion.cpp: In function 'void genseq(int, int, std::vector<int>&)':
potion.cpp:122:45: warning: 'slot' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |     for (pair<int,int> i : cj::small[x][slot]){
      |                                             ^

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30