Submission #655365

#	Time	Username	Problem	Language	Result	Execution time	Memory
655365		SpaimaCarpatilor	Fireworks (APIO16_fireworks)	C++17	100 / 100	293 ms	100164 KiB

fireworks

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <queue>
#include <cmath>
#include <iomanip>
#include <iterator>
#include <bitset>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <chrono>
#include <random>
#include <array>
#include <functional>
#include <random>

///1:54
using namespace std;

const int maxN = 300009;
int N, M, t[maxN], d[maxN], sz[maxN];
vector<int> v[maxN];
const bool DBG = 0;

namespace brute {
    const int maxK = 100;
    long long bruteDp[maxN][100];

    int mod(int x) { return (x < 0 ? -x : x); }

    void doBrute() {
        for (int i = N; i >= 1; i--) {
            if (v[i].empty()) {
                for (int j = 0; j < maxK; j++)
                    bruteDp[i][j] = j;
            } else {
                for (int j = 0; j < maxK; j++) {
                    for (auto it: v[i]) {
                        long long best = 0;
                        for (int k = 0; k <= j; k++) {
                            long long curr = bruteDp[it][k] + mod((j - k) - d[it]);
                            if (curr < best || k == 0)
                                best = curr;
                        }
                        bruteDp[i][j] += best;
                    }
                    if (j > 0)
                        bruteDp[i][j] = min(bruteDp[i][j], bruteDp[i][j - 1] + 1);
                }
            }
        }
        long long ans = bruteDp[1][0];
        for (int i = 1; i < maxK; i++)
            ans = min(ans, bruteDp[1][i]);
        printf("brute: %lld\n", ans);
    }
};

void dfsSz(int nod) {
    int pos = 0, heaviest = -1;
    sz[nod] = 1;
    for (auto it : v[nod]) {
        dfsSz(it);
        sz[nod] += sz[it];
        if (heaviest == -1 || sz[it] > sz[v[nod][heaviest]])
            heaviest = pos;
        pos ++;
    }
    if (heaviest > 0)
        swap(v[nod][heaviest], v[nod][0]);
}

struct dpFunction {
    multiset<long long> S;
    long long platformLength = 0, smallest = 0;

    long long platformStart() {
        if (S.empty()) return 0;
        return *S.rbegin();
    }

    void addD(int d) {
        if (S.empty()) {
            S.insert(d);
            return ;
        }
        auto it = S.end(); it --;
        S.insert(*it + d);
        S.erase(it);
    }

    void operator += (const dpFunction& other) {
        for (auto it : other.S)
            S.insert(it);
        smallest += other.smallest;
    }

    void print() {
        printf("{");
        for (auto it : S)
            printf("%lld,", it);
        printf("\b} min=%lld, platform=%lld", smallest, platformLength);
    }

    void printVals(int nodeToCompare = -1) {
        if (S.empty()) {
            printf("flat at [%lld, %lld]\n", platformStart(), platformStart() + platformLength);
            return ;
        }
        vector<long long> f(max<int>(platformStart() + platformLength + 10, brute::maxK), 0LL);
        auto it = S.end(); it --;
        int slope = 0;
        long long curr = smallest;
        for (int i=platformStart() + platformLength; i>=0; i--) {
            while (it != S.begin() && *it >= i)
                slope ++, it --;
            f[i] = curr, curr += slope + (*it >= i);
        }
        curr = smallest;
        for (int i=platformStart() + platformLength + 1; i<f.size(); i++)
            curr ++, f[i] = curr;
        if (nodeToCompare != -1) {
            bool areSame = 1;
            for (int i = 0; i < f.size(); i++)
                areSame &= (f[i] == brute::bruteDp[nodeToCompare][i]);
            if (!areSame) {
                printf("WA %d:\n", nodeToCompare);
                for (int i = 0; i < f.size(); i++)
                    printf("%2d ", i);
                printf("\n");
                for (auto it: f)
                    printf("%2lld ", it);
                printf("\ninstead of \n");
                for (int i = 0; i < f.size(); i++)
                    printf("%2lld ", brute::bruteDp[nodeToCompare][i]);
                exit(0);
            }
        } else {
            for (auto it : f)
                printf("%2d ", it);
            printf("\n");
        }
    }
}dp[20];

void solve(int nod, int lev) {
    if (v[nod].empty()) {
        dp[lev] = dpFunction();
        return ;
    }
    vector<long long> rightEnds;
    for (auto it : v[nod]) {
        if (it != v[nod][0]) {
            dp[lev + 1] = dpFunction();
            solve(it, lev + 1);
            dp[lev + 1].addD(d[it]);
            dp[lev] += dp[lev + 1];
            rightEnds.push_back(dp[lev + 1].platformStart() + dp[lev + 1].platformLength);
        } else {
            solve(it, lev);
            dp[lev].addD(d[it]);
            rightEnds.push_back(dp[lev].platformStart() + dp[lev].platformLength);
        }
    }
    if (DBG) {
        printf("rightEnds:[");
        for (auto it: rightEnds)
            printf("%lld ", it);
        printf("\b]\n");
        printf("before rightEnds: "), dp[lev].print(), printf("\n");
        dp[lev].printVals();
    }
    sort(rightEnds.rbegin(), rightEnds.rend());
    for (auto x : rightEnds) {
        dp[lev].S.insert(x);
        //dp[lev].print(), printf("following %d\n", x);
        auto it2 = dp[lev].S.end(); it2 --;
        auto it = it2; it --;
        dp[lev].platformLength = *it2 - *it;
        dp[lev].smallest += *it2 - x;
        dp[lev].S.erase(it2);
    }
    if (DBG) {
        printf("node %d: "), dp[lev].print(), printf("\n");
        dp[lev].printVals(nod);
    }
}

int main() {
    //freopen("../input", "r", stdin);
    //freopen("../output", "w", stdout);

    scanf("%d %d", &N, &M), N += M;
    for (int i=2; i<=N; i++) {
        scanf("%d %d", &t[i], &d[i]);
        v[t[i]].push_back(i);
    }
    if (DBG) brute::doBrute();
    dfsSz(1);
    solve(1, 0);
    printf("%lld\n", dp[0].smallest);
    return 0;
}

/*const int seed = time (0);
mt19937 gen (seed);
long long getRand(long long a, long long b) {return uniform_int_distribution < long long > (a, b) (gen);}*/

Compilation message (stderr)

fireworks.cpp: In member function 'void dpFunction::printVals(int)':
fireworks.cpp:129:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i=platformStart() + platformLength + 1; i<f.size(); i++)
      |                                                          ~^~~~~~~~~
fireworks.cpp:133:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             for (int i = 0; i < f.size(); i++)
      |                             ~~^~~~~~~~~~
fireworks.cpp:137:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |                 for (int i = 0; i < f.size(); i++)
      |                                 ~~^~~~~~~~~~
fireworks.cpp:143:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |                 for (int i = 0; i < f.size(); i++)
      |                                 ~~^~~~~~~~~~
fireworks.cpp:149:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  149 |                 printf("%2d ", it);
      |                         ~~^    ~~
      |                           |    |
      |                           int  long long int
      |                         %2lld
fireworks.cpp: In function 'void solve(int, int)':
fireworks.cpp:193:23: warning: format '%d' expects a matching 'int' argument [-Wformat=]
  193 |         printf("node %d: "), dp[lev].print(), printf("\n");
      |                      ~^
      |                       |
      |                       int
fireworks.cpp: In function 'int main()':
fireworks.cpp:202:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |     scanf("%d %d", &N, &M), N += M;
      |     ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         scanf("%d %d", &t[i], &d[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45