oj.uz

Submission #1008456

# Submission time Handle Problem Language Result Execution time Memory
1008456 2024-06-26T12:44:15 Z 12345678 Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 47296 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);
    for (int i=0; i<(1<<N); i++)
    {
        ll cst=0, res=0;
        vector<int> vsa(N), vsb(N);
        for (int j=0; j<N; j++) 
        {
            if (i&(1<<j))
            {
                vsa[j]=vsb[j]=1;
                cst+=max(a[j], b[j]);
                res+=2;
                int tmp=j;
                while (tmp!=X)
                {
                    if (!vsa[tmp]) vsa[tmp]=1, res++, cst+=a[tmp];
                    tmp=pa[tmp];
                }
                tmp=j;
                while (tmp!=Y)
                {
                    if (!vsb[tmp]) vsb[tmp]=1, res++, cst+=b[tmp];
                    tmp=pb[tmp];
                }
            }
        }
        if (cst>K) continue; 
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        for (int i=0; i<N; i++) if (!vsa[i]) pq.push(a[i]);
        for (int i=0; i<N; i++) if (!vsb[i]) pq.push(b[i]);
        while (!pq.empty()&&cst+pq.top()<=K) res++, cst+=pq.top(), pq.pop();
        mx=max(mx, res);
    }
    return mx;
}

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 2 ms 4956 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 41124 KB Output is correct
2 Correct 98 ms 47296 KB Output is correct
3 Execution timed out 1055 ms 10404 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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