oj.uz

Submission #1008936

# Submission time Handle Problem Language Result Execution time Memory
1008936 2024-06-27T05:57:49 Z 12345678 Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 38064 KB 
#include "closing.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#pragma gcc-optimize("O3, unrolls-loops")

const int nx=2e5+5;

vector<pair<ll, ll>> g[nx];

void dfs(int u, int p, ll cw, vector<ll> &pa, vector<ll> &x)
{
    pa[u]=p;
    x[u]=cw;
    for (auto [v, w]:g[u]) if (v!=p) dfs(v, u, cw+w, pa, x);
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    ll mx=0;
    for (int i=0; i<N; i++) g[i].clear();
    for (int i=0; i<N-1; i++) g[U[i]].push_back({V[i], W[i]}), g[V[i]].push_back({U[i], W[i]});
    vector<ll> pa(N), pb(N), a(N), b(N);
    dfs(X, X, 0, pa, a);
    dfs(Y, Y, 0, pb, b);
    priority_queue<ll, vector<ll>, greater<ll>> pq2;
    for (int i=0; i<N; i++) pq2.push(a[i]), pq2.push(b[i]);
    ll tmp=K;
    while (!pq2.empty()&&pq2.top()<=tmp) mx++, tmp-=pq2.top(), pq2.pop();
    vector<ll> path;
    tmp=Y;
    while (pa[tmp]!=X) path.push_back(pa[tmp]), tmp=pa[tmp];
    reverse(path.begin(), path.end());
    ll sz=path.size();
    for (int i=0; i<sz; i++)
    {
        for (int j=i; j<sz; j++)
        {
            ll c=K, res=0;
            priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
            vector<ll> vs(N);
            for (int k=i; k<=j; k++) vs[path[k]]=1, c-=max(a[path[k]], b[path[k]]), res+=2;
            for (int k=0; k<i; k++) vs[path[k]]=1, res++, c-=a[path[k]];
            for (int k=j+1; k<sz; k++) vs[path[k]]=1, res++, c-=b[path[k]];
            for (int k=i; k<=j; k++) for (auto [v, w]:g[path[k]]) if (!vs[v]) pq.push({max(a[v], b[v]), v});
            if (c<0) continue;
            while (!pq2.empty()) pq2.pop();
            for (int i=0; i<N; i++) if (!vs[i]) pq2.push(a[i]), pq2.push(b[i]);
            ll tmpres=res, tmpc=c;
            while (!pq2.empty()&&tmpc>=pq2.top()) tmpres++, tmpc-=pq2.top(), pq2.pop();
            mx=max(mx, tmpres);
            while (!pq.empty())
            {
                auto [w, u]=pq.top();
                pq.pop();
                c-=w;
                vs[u]=1;
                res+=2;
                for (auto [v, cw]:g[u]) if (!vs[v]) pq.push({max(a[v], b[v]), v});
                if (c<0) continue;
                while (!pq2.empty()) pq2.pop();
                for (int i=0; i<N; i++) if (!vs[i]) pq2.push(a[i]), pq2.push(b[i]);
                tmpres=res, tmpc=c;
                while (!pq2.empty()&&tmpc>=pq2.top()) tmpres++, tmpc-=pq2.top(), pq2.pop();
                mx=max(mx, tmpres);
            }
        }
    }
    return mx;
}

/*
1
6 0 3 20
0 1 2
1 2 5
2 3 6
1 4 5
1 5 2
*/

Compilation message

closing.cpp:7: warning: ignoring '#pragma gcc ' [-Wunknown-pragmas]
    7 | #pragma gcc-optimize("O3, unrolls-loops")
      |

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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