Submission #128170

#	Time	Username	Problem	Language	Result	Execution time	Memory
128170		aleks5d	Fireworks (APIO16_fireworks)	C++14	7 / 100	2 ms	380 KiB

fireworks

#pragma GCC omptimize("unroll-loops")
#pragma optimize("SEX_ON_THE_BEACH")
#pragma GCC optimize("no-stack-protector")
#pragma comment(linker, "/STACK:1000000000")
#include<bits/stdc++.h>

using namespace std;

//#define need_tree

#ifdef need_tree
    #include<ext/pb_ds/assoc_container.hpp>
    using namespace __gnu_pbds;
    template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif // need_tree

using ll = unsigned long long int;
using ull = unsigned long long int;
using dd = long double;
using ldd = long double;
using si = short int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

ll get_seed(string s)
{
    ll ans = 0;
    for (int i = 0; i < s.size(); ++i)
        ans += s[i];
    return ans;
}

int popcount(int x)
{
    return __builtin_popcount(x);
}

ll popcountll(ll x)
{
    return __builtin_popcount(x);
}

#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second


// debug defines
#ifdef HOME
    int jjj;
    #define PO cout << "Pomelo" << endl;
    #define OL cout << "Oliva" << endl;
    #define debug(x) cout << #x << " " << x << endl;
    #define debug_p(x) cout << #x << " " << x.ff << " " << x.ss << endl;
    #define debug_v(x) cout << #x << " "; for (auto iii : x) cout << iii << " "; cout << endl;
    #define debug_vp(x) cout << #x << " "; for (auto ii : x) cout << '[' << ii.ff << " " << ii.ss << ']'; cout << endl;
    #define wait() cin >> jjj;
#else
    #define PO 0;
    #define OL 0;
    #define debug(x) 0;
    #define debug_p(x) 0;
    #define debug_vp(x) 0;
    #define debug_v(x) 0;
    #define debug_vp(x) 0;
    #define wait() 0;
#endif // HOME
// end of debug defines

ll normilize(vector<pair<ll, ll>>& arr)
{
    if (arr.size() == 1)
        return 0;
    vector<pair<ll, int>> tp;
    for (int i = 0; i < arr.size(); ++i)
    {
        tp.push_back({arr[i].ff, 1});
        tp.push_back({arr[i].ss, -1});
    }
    sort(all(tp));
    int n = arr.size();
    int nw = 0;
    for (int i = 0; i < tp.size(); ++i)
    {
        if (tp[i].ss == 1)
        {
            n--;
        }
        else
        {
            nw++;
        }
        if (nw >= n)
        {
            ll tmp = 0;
            ll x = tp[i].ff;
            debug(x);
            for (int i = 0; i < arr.size(); ++i)
            {
                if (arr[i].ff > x)
                {
                    tmp += arr[i].ff - x;
                }
                else if (arr[i].ss < x)
                {
                    tmp += x - arr[i].ss;
                }
            }
            arr.clear();
            arr.push_back({tp[i].ff, tp[i + 1].ff});
            return tmp;
        }
    }

}

void solve(int i)
{
    int n, m;
    cin >> n >> m;
    vector<int> pre(n + m);
    vector<ll> cost(n + m);
    vector<ll> dp(n + m);
    vector<vector<pair<ll, ll>>> can(n + m);
    pre[0] = -1;
    for (int i = 1; i < n; ++i)
    {
        cin >> pre[i] >> cost[i];
        --pre[i];
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> pre[i + n] >> cost[i + n];
        --pre[i + n];
        dp[i + n] = 0;
        can[pre[i + n]].push_back({cost[i + n], cost[i + n]});
    }
    for (int i = n - 1; i > 0; --i)
    {
        debug(i + 1);
        debug_vp(can[i]);
        debug(dp[i]);
        dp[i] += normilize(can[i]);
        debug(dp[i]);
        debug_vp(can[i]);
        debug(cost[i]);

        can[pre[i]].push_back({can[i][0].ff + cost[i], can[i][0].ss + cost[i]});
        dp[pre[i]] += dp[i];
    }
    dp[0] += normilize(can[0]);
    cout << dp[0];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    int t;
    t = 1;
    //cin >> t;
    for (int i = 0; i < t; ++i)
        solve(i);

    return 0;
}

/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/

Compilation message (stderr)

fireworks.cpp:1:0: warning: ignoring #pragma GCC omptimize [-Wunknown-pragmas]
 #pragma GCC omptimize("unroll-loops")
 
fireworks.cpp:2:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("SEX_ON_THE_BEACH")
 
fireworks.cpp:4:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:1000000000")
 
fireworks.cpp: In function 'll get_seed(std::__cxx11::string)':
fireworks.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i)
                     ~~^~~~~~~~~~
fireworks.cpp: In function 'll normilize(std::vector<std::pair<long long unsigned int, long long unsigned int> >&)':
fireworks.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < arr.size(); ++i)
                     ~~^~~~~~~~~~~~
fireworks.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < tp.size(); ++i)
                     ~~^~~~~~~~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
fireworks.cpp:97:13: note: in expansion of macro 'debug'
             debug(x);
             ^~~~~
fireworks.cpp:98:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < arr.size(); ++i)
                             ~~^~~~~~~~~~~~
fireworks.cpp: In function 'void solve(int)':
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
fireworks.cpp:140:9: note: in expansion of macro 'debug'
         debug(i + 1);
         ^~~~~
fireworks.cpp:65:26: warning: statement has no effect [-Wunused-value]
     #define debug_vp(x) 0;
                          ^
fireworks.cpp:141:9: note: in expansion of macro 'debug_vp'
         debug_vp(can[i]);
         ^~~~~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
fireworks.cpp:142:9: note: in expansion of macro 'debug'
         debug(dp[i]);
         ^~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
fireworks.cpp:144:9: note: in expansion of macro 'debug'
         debug(dp[i]);
         ^~~~~
fireworks.cpp:65:26: warning: statement has no effect [-Wunused-value]
     #define debug_vp(x) 0;
                          ^
fireworks.cpp:145:9: note: in expansion of macro 'debug_vp'
         debug_vp(can[i]);
         ^~~~~~~~
fireworks.cpp:61:23: warning: statement has no effect [-Wunused-value]
     #define debug(x) 0;
                       ^
fireworks.cpp:146:9: note: in expansion of macro 'debug'
         debug(cost[i]);
         ^~~~~
fireworks.cpp: In function 'll normilize(std::vector<std::pair<long long unsigned int, long long unsigned int> >&)':
fireworks.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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