Submission #842148

#	Time	Username	Problem	Language	Result	Execution time	Memory
842148		danikoynov	Closing Time (IOI23_closing)	C++17	75 / 100	1012 ms	1021176 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;

vector < pair < int, ll > > adj[maxn];
ll dist[2][maxn];
int n;

void bfs(int s, ll arr[])
{
    queue < int > q;
    for (int i = 0; i < n; i ++)
        arr[i] = -1;

    arr[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        for (pair < int, ll > nb : adj[v])
        {
            if (arr[nb.first] == -1)
            {
                arr[nb.first] = arr[v] + nb.second;
                q.push(nb.first);
            }
        }
    }
}
const ll inf = 1e18;




ll value[maxn];
ll dp[2][2][3010][3010 * 2], sub[maxn], temp[2][2][maxn * 2];
int used[maxn];
/**

*/
vector < int > st[maxn];
void dfs(int v, int t)
{
    ///cout << "dfs " << v << endl;
    sub[v] = 1;
    used[v] = 1;
    if (t != v)
        st[t].push_back(v);

    for (int j = 0; j <= 2; j ++)
        for (int d = 0; d < 2; d ++)
            for (int z = 0; z < 2; z ++)
                dp[d][z][v][j] = inf;
    dp[0][0][v][0] = 0;
    dp[1][0][v][1] = dist[0][v];
    dp[0][1][v][1] = dist[1][v];
    dp[1][1][v][2] = max(dist[0][v], dist[1][v]);

    for (pair < int, ll > nb : adj[v])
    {
        if (used[nb.first])
            continue;

        dfs(nb.first, t);
        int u = nb.first;
        for (int i = 0; i <= (sub[u] + sub[v]) * 2; i ++)
            for (int x = 0; x < 2; x ++)
                for (int y = 0; y < 2; y ++)
                    temp[x][y][i]= inf;

        for (int i = 0; i <= sub[v] * 2; i ++)
            for (int j = 0; j <= sub[u] * 2; j ++)
                for (int d = 0; d < 2; d ++)
                    for (int z = 0; z < 2; z ++)
                        for (int x = 0; x <= d; x ++)
                            for (int y = 0; y <= z; y ++)
                            {

                                temp[d][z][i + j] = min(temp[d][z][i + j], dp[d][z][v][i] + dp[x][y][u][j]);
                            }

        for (int i = 0; i <= (sub[v] + sub[u]) * 2; i ++)
            for (int x = 0; x < 2; x ++)
                for (int y = 0; y < 2; y ++)
                    dp[x][y][v][i] = temp[x][y][i];
        sub[v] += sub[u];
    }
}

ll fp[3][3010][3010 * 2], tp[3010 * 2];
void unite(ll arr1[], int sz1, ll arr2[], int sz2, ll res[])
{
    for (int i = 0; i <= (sz1 + sz2) * 2; i ++)
    {
        tp[i] = inf;
    }

    for (int i = 0; i <= sz1 * 2; i ++)
        for (int j = 0; j <= sz2 * 2; j ++)
            tp[i + j] = min(tp[i + j], arr1[i] + arr2[j]);

    for (int i = 0; i <= (sz1 + sz2) * 2; i ++)
        res[i] = tp[i];
}

vector < int > path;
bool get_path(int v, int p, int target)
{
    if (v == target)
    {
        path.push_back(v);
        return true;
    }

    for (pair < int, ll > nb : adj[v])
    {
        if (nb.first == p)
            continue;
        if (get_path(nb.first, v, target))
        {
            path.push_back(v);
            return true;
        }
    }
    return false;
}

int ans, loc[maxn];

ll td[3][3][maxn];
int max_score(int N, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W)
{

    for (int i = 0; i < N; i ++)
    {
        dist[0][i] = dist[1][i] = 0;
        adj[i].clear();
        used[i] = 0;
        value[i] = 0;
    }
    ans = 0;
    n = N;
    for (int i = 0; i < N - 1; i ++)
    {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }

    bfs(X, dist[0]);
    bfs(Y, dist[1]);

    path.clear();
    get_path(Y, -1, X);
    for (int cur : path)
        used[cur] = 1;
    for (int cur : path)
        dfs(cur, cur);

    vector < ll > vec;
    for (int i = 0; i < N; i ++)
    {
        vec.push_back(dist[0][i]);
        vec.push_back(dist[1][i]);
    }

    sort(vec.begin(), vec.end());
    ll sum = 0;
    for (int i = 0; i < vec.size(); i ++)
    {
        sum += vec[i];
        if (sum > K)
            break;
        ans = max(ans, i + 1);
    }


    for (int id = (int)(path.size()) - 1; id >= 0; id --)
    {
        int ver = path[id];
        loc[ver] = sub[ver];
        for (int j = 0; j <= 2 * sub[ver]; j ++)
        {
            fp[2][ver][j] = dp[0][1][ver][j];
            fp[1][ver][j] = dp[1][1][ver][j];
            fp[0][ver][j] = dp[1][0][ver][j];
        }


        if (id + 1 == path.size())
            continue;

        for (int j = 0; j < 3; j ++)
        {
            for (int p = j; p < 3; p ++)
            {
                unite(fp[j][ver], loc[ver], fp[p][path[id + 1]], loc[path[id + 1]], td[j][p]);
                /**for (int i = 0; i <= N * 2; i ++)
                    cout << td[j][p][i] << " ";
                cout << endl;*/
            }
        }
        ///cout << "step " << ver << endl; for (int i = 0; i <= 2* (loc[ver] + loc[path[id + 1]]); i ++)
        ///cout << td[0][1][i] << endl;
        for (int j = 0; j < 3; j ++)
        {
            for (int i = 0; i <= 2 * (loc[ver] + loc[path[id + 1]]); i ++)
                fp[j][ver][i] = inf;
            for (int p = j; p < 3; p ++)
            {



                for (int i = 0; i <= 2 * (loc[ver] + loc[path[id + 1]]); i ++)
                {

                    fp[j][ver][i] = min(fp[j][ver][i], td[j][p][i]);
                }
            }
        }


        loc[ver] += loc[path[id + 1]];
    }


    for (int i = 0; i <= N * 2; i ++)
    {
        ///cout << fp[0][path[0]][i] <<  " : " << i << endl;
        if (fp[0][path[0]][i] <= K)
            ans = max(ans, i);
    }

    for (int i = 0; i <= N * 2; i ++)
    {
        ///cout << fp[1][path[0]][i] <<  " : " << i << endl;
        if (fp[1][path[0]][i] <= K)
            ans = max(ans, i);
    }
    return ans;

}

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:174:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for (int i = 0; i < vec.size(); i ++)
      |                     ~~^~~~~~~~~~~~
closing.cpp:195:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |         if (id + 1 == path.size())
      |             ~~~~~~~^~~~~~~~~~~~~~

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