oj.uz

Submission #842479

# Submission time Handle Problem Language Result Execution time Memory
842479 2023-09-03T00:13:27 Z CodePlatina Closing Time (IOI23_closing) C++17
8 / 100
 112 ms 37360 KB 
#include "closing.h"
#include <vector>
#include <iostream>
#include <algorithm>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ff first
#define ss second
using namespace std;

vector<pii> gph[202020];
long long D1[202020];
long long D2[202020];
bool path[202020];
long long L;

void dfs1(int x, int p, long long w)
{
    D1[x] = w;
    for(auto [y, z] : gph[x]) if(y != p) dfs1(y, x, w + z);
}
void dfs2(int x, int p, long long w)
{
    D2[x] = w;
    for(auto [y, z] : gph[x]) if(y != p) dfs2(y, x, w + z);
}
bool dfs(int x, int p, int y)
{
    if(x == y)
    {
        path[x] = true;
        return true;
    }

    for(auto [z, w] : gph[x]) if(z != p)
    {
        if(dfs(z, x, y))
        {
            L += w;
            path[x] = true;
            return true;
        }
    }

    return false;
}

int calc(vector<long long> A, vector<pll> B, long long K)
{
    vector<pll> C;
    for(auto [x, y] : B) 
    {
        if(y - x >= x) A.push_back(x), A.push_back(y - x);
        else B.push_back({x, y});
    }

    sort(A.begin(), A.end());
    //upper_bound remaining cost on D and get score
    vector<long long> D;
    if(A.size()) D.push_back(A[0]);
    for(int i = 1; i < (int)A.size() && D.back() + A[i] <= K; ++i) D.push_back(D.back() + A[i]);

    sort(C.begin(), C.end(), [](pll x, pll y) { return x.ss < y.ss; });
    int N = C.size();
    //E: prefix max of y - x, F: suffix min of x
    vector<long long> E(N), F(N);
    for(int i = 0; i < N; ++i)
    {
        E[i] = C[i].ss - C[i].ff;
        if(i) E[i] = max(E[i], E[i - 1]);
    }
    for(int i = N - 1; i >= 0; --i)
    {
        F[i] = C[i].ff;
        if(i < N - 1) F[i] = min(F[i], F[i + 1]);
    }

    int ret = 0;
    long long sum = 0;
    for(int i = 0; i <= N; ++i)
    {
        if(sum <= K) ret = max(ret, 2 * i + int(upper_bound(D.begin(), D.end(), K - sum) - D.begin()));
        if(i && sum - E[i - 1] <= K) ret = max(ret, 2 * i - 1 + int(upper_bound(D.begin(), D.end(), K - sum + E[i - 1]) - D.begin()));
        if(i < N && sum + F[i] <= K) ret = max(ret, 2 * i + 1 + int(upper_bound(D.begin(), D.end(), K - sum - F[i]) - D.begin()));
        if(sum > K) break;
        if(i < N) sum += C[i].ss;
    }

    return ret;
}

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) gph[i].clear(), D1[i] = 0, D2[i] = 0, path[i] = false;
    L = 0;

    for(int i = 0; i < N - 1; ++i)
    {
        gph[U[i]].push_back({V[i], W[i]});
        gph[V[i]].push_back({U[i], W[i]});
    }

    dfs1(X, X, 0);
    dfs2(Y, Y, 0);
    dfs(X, X, Y);

    int ret = 0;
    vector<long long> WG;

    for(int i = 0; i < N; ++i) WG.push_back(min(D1[i], D2[i]));
    ret = max(ret, calc(WG, vector<pll>(), K));
    WG.clear();

    // cout << ret << endl;

    vector<long long> A;
    vector<pll> B;
    int cnt = 0; long long sum = 0;
    for(int i = 0; i < N; ++i)
    {
        if(path[i]) ++cnt, sum += min(D1[i], D2[i]), A.push_back(max(D1[i], D2[i]) - min(D1[i], D2[i]));
        else B.push_back({min(D1[i], D2[i]), max(D1[i], D2[i])});
    }
    // cout << K - sum << endl;
    // cout << cnt << endl;
    // for(auto [x, y] : A) cout << x << ' ' << y << endl;
    if(sum <= K) ret = max(ret, cnt + calc(A, B, K - sum));
    WG.clear();

    // cout << ret << endl;

    // cnt = 0; sum = 0;
    // for(int i = 0; i < N; ++i)
    // {
    //     if(D1[i] <= D2[i]) WG.push_back(D1[i]), WG.push_back(D2[i] - D1[i]);
    //     else
    //     {
    //         if(path[i]) ++cnt, sum += D2[i];
    //         else WG.push_back(D2[i]);
    //     }
    // }
    // if(sum <= K) ret = max(ret, cnt + calc(WG, K - sum));
    // WG.clear();

    // cout << ret << endl;

    // cnt = 0; sum = 0;
    // for(int i = 0; i < N; ++i)
    // {
    //     if(D1[i] <= D2[i])
    //     {
    //         if(path[i]) ++cnt, sum += D1[i], WG.push_back(D2[i] - D1[i]);
    //         else WG.push_back(D1[i]), WG.push_back(D2[i] - D1[i]);
    //     }
    //     else
    //     {
    //         if(path[i]) ++cnt, sum += D2[i], WG.push_back(D1[i] - D2[i]);
    //         else WG.push_back(D2[i]), WG.push_back(D1[i] - D2[i]);
    //     }
    // }
    // if(sum <= K) ret = max(ret, cnt + calc(WG, K - sum));
    // WG.clear();

    // cout << ret << endl;

    return ret;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 35320 KB Output is correct
2 Correct 112 ms 37360 KB Output is correct
3 Correct 59 ms 10832 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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