oj.uz

Submission #861704

# Submission time Handle Problem Language Result Execution time Memory
861704 2023-10-16T16:51:07 Z faustaadp Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 34832 KB 
#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++;
    }
    // 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;
    }
    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[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);
    }
    if(perlu)
        return max((int)ret, max_score(N, Y, X, K, U, V, W));
    else
        return ret;
}

Compilation message

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:119: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]
  119 |             for(ll j = 0; j < cal.size(); j++)
      |                           ~~^~~~~~~~~~~~
closing.cpp:160:25: 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]
  160 |         for(ll j = 0; j < cal.size(); j++)
      |                       ~~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 34832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9560 KB Output is correct
3 Incorrect 2 ms 9564 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
4 Halted 0 ms 0 KB -