Submission #861705

#	Time	Username	Problem	Language	Result	Execution time	Memory
861705		faustaadp	Closing Time (IOI23_closing)	C++17	21 / 100	1090 ms	58336 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#include <vector>
const ll NN = 2e5 + 5;
vector<pll> v[NN];
ll isi[NN], py[NN], te, ps[NN];
vector<ll> isi2;
void dfs(ll pos, ll par, ll now)
{
    te++;
    isi[te] = pos;
    py[pos] = te;
    ps[te] = now;
    for(auto nx : v[pos])
    {
        if(nx.fi != par)
            dfs(nx.fi, pos, now + nx.se);
    }
}
void dfs2(ll pos, ll par, ll now)
{
    isi2.pb(now);
    for(auto nx : v[pos])
    {
        if(nx.fi != par)
            dfs2(nx.fi, pos, now + nx.se);
    }
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    // cout << X << " " << Y << "_\n";
    ll perlu = (X < Y);
    te = 0;
    ll R = 0;
    for(ll i = 0; i < N; i++)
    {
        py[i] = 0;
        isi[i + 1] = 0;
        v[i].clear();
    }
    isi2.clear();

    for(ll i = 0; i < V.size(); i++)
    {
        // cout << U[i] << " " << V[i] << "    " << W[i] << "@\n";
        v[U[i]].pb(mp(V[i], W[i]));
        v[V[i]].pb(mp(U[i], W[i]));
    }
    for(ll i = 0; i < N; i++)
        if(v[i].size() == 1)
        {
            R = i;
            break;
        }
    dfs(R, R, 0);
    dfs2(X, X, 0);
    dfs2(Y, Y, 0);
    ll now = K, ret = 0;
    sort(isi2.begin(), isi2.end());
    for(ll i = 0; i < 2 * N; i++)
    {
        if(isi2[i] > now)
            break;
        now -= isi2[i];
        ret++;
    }
    // ret = 0;
    // return ret;
    if(py[X] > py[Y])
        swap(X, Y);
    // cout << py[X] << "  " << py[Y] << " @\n";
    for(ll i = py[X]; i <= py[Y]; i++)
    {
        ll sisa = K, now = 0;
        for(ll j = py[X]; j <= i; j++)
        {
            now++;
            sisa -= ps[j] - ps[py[X]];
        }
        for(ll j = i + 1; j <= py[Y]; j++)
        {
            now++;
            sisa -= ps[py[Y]] - ps[j];
        }

        for(ll l = 1; l <= py[X]; l++)
        {   
            vector<ll> cal;
            ll sisa2 = sisa;
            ll now2 = now;
            // cout << now << "@\n";
            for(ll j = l; j < py[X]; j++)
            {
                sisa2 -= ps[py[X]] - ps[j];
                now2++;
                cal.pb(ps[py[Y]] - ps[py[X]]); // Y
            }

            for(ll j = py[X]; j <= i; j++)
                cal.pb(max(0LL, (ps[py[Y]] - ps[j]) - (ps[j] - ps[py[X]])));

            for(ll j = py[Y] + 1; j <= N; j++)
                cal.pb(ps[j] - ps[py[Y]]);

            // cout << i << " " << l << "@\n";
            // cout << cal.size() << " " << now2 << "_\n";
            if(sisa2 < 0)
                continue;

            // cout << i << " " << now << " " << sisa << "_\n";
            sort(cal.begin(), cal.end());
            for(ll j = 0; j < cal.size(); j++)
            {
                if(cal[j] > sisa2)
                    break;
                sisa2 -= cal[j];
                now2++;
            }
            ret = max(ret, now2);
        }
    }

    ll sisa = K;
    now = 0;
    for(ll i = py[X]; i <= py[Y]; i++)
    {
        sisa -= max(ps[py[Y]] - ps[i], ps[i] - ps[py[X]]);
        now += 2;
    }
    // cout << sisa << " " << now << "__\n";
    for(ll l = 1; l <= py[X]; l++)
    {   
        for(ll i = py[Y] + 1; i <= N; i++)
        {
            vector<ll> cal;
            ll sisa2 = sisa;
            ll now2 = now;
            // cout << now << "@\n";
            for(ll j = l; j < py[X]; j++)
            {
                sisa2 -= ps[py[X]] - ps[j];
                now2++;
                cal.pb(ps[py[Y]] - ps[py[X]]); // Y
            }

            for(ll j = py[Y] + 1; j <= i; j++)
            {
                sisa2 -= ps[j] - ps[py[Y]];
                now2++;
                cal.pb(ps[py[Y]] - ps[py[X]]);
            }

            // cout << i << " " << l << "@\n";
            // cout << l << "   " << cal.size() << " " << now2 << "_\n";
            if(sisa2 < 0)
                continue;

            // cout << i << " " << now << " " << sisa << "_\n";
            sort(cal.begin(), cal.end());
            for(ll j = 0; j < cal.size(); j++)
            {
                if(cal[j] > sisa2)
                    break;
                sisa2 -= cal[j];
                now2++;
            }
            ret = max(ret, now2);
        }
    }
    if(perlu)
        return max((int)ret, max_score(N, Y, X, K, U, V, W));
    else
        return ret;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:51:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(ll i = 0; i < V.size(); i++)
      |                   ~~^~~~~~~~~~
closing.cpp:120:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for(ll j = 0; j < cal.size(); j++)
      |                           ~~^~~~~~~~~~~~
closing.cpp:168:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             for(ll j = 0; j < cal.size(); j++)
      |                           ~~^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17