oj.uz

Submission #843664

# Submission time Handle Problem Language Result Execution time Memory
843664 2023-09-04T11:26:18 Z Boas Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 46032 KB 
#include "closing.h"
using namespace std;
#include <bits/stdc++.h>
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef vector<sii> vsii;
typedef tuple<ll, ll, ll, bool> item;

#define ALL(x) (x).begin(), x.end()
#define loop(x, i) for (int i = 0; i < x; i++)

void getDist(int i, ll d, vi &dist, const vsii &adj)
{
    dist[i] = d;
    for (auto [j, w] : adj[i])
    {
        if (dist[j] != -1)
            continue;
        getDist(j, dist[i] + w, dist, adj);
    }
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W)
{
    vsii adj(N);
    loop(N - 1, i)
    {
        adj[U[i]].insert({V[i], W[i]});
        adj[V[i]].insert({U[i], W[i]});
    }
    vi distX(N, -1), distY(N, -1);
    distX[X] = 0;
    distY[Y] = 0;
    getDist(X, 0, distX, adj);
    getDist(Y, 0, distY, adj);
    int max = 0;
    // vb visX(N);
    // vb visY(N);
    for (int xleft = 0; X - xleft >= 0; xleft++)
    {
        for (int xright = 0; X + xright < N; xright++)
        {
            for (int yleft = 0; yleft <= Y; yleft++)
            {
                ll sum = 0;
                for (int i = 0; i < Y; i++)
                {
                    ll v = 0;
                    if (X - xleft <= i && i <= X + xright)
                    {
                        v = std::max(v, distX[i]);
                    }
                    if (Y - yleft <= i)
                    {
                        v = std::max(v, distY[i]);
                    }
                    sum += v;
                }
                int yright = 0;
                for (; Y + yright < N; yright++)
                {
                    ll v = distY[Y + yright];
                    if (X + xright >= Y + yright)
                        v = std::max(v, distX[Y + yright]);
                    sum += v;
                    if (K - sum < 0)
                        break;
                    int count = 2 + xright + yright + xleft + yleft;
                    if (count > max)
                    {
                        cerr << "Solution has: " << xleft << ' ' << xright << ' ' << yleft << ' ' << yright << endl;
                        max = count;
                    }
                }
            }
        }
    }
    cerr << endl;
    return max;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '9'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '9'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '9'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '9'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '9'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '9'
2 Halted 0 ms 0 KB -