oj.uz

Submission #1027817

# Submission time Handle Problem Language Result Execution time Memory
1027817 2024-07-19T10:22:56 Z Gray Closing Time (IOI23_closing) C++17
8 / 100
 92 ms 46540 KB 
#include "closing.h"
// #include <iostream>
#include <climits>
#include <queue>
#include <stack>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
using namespace std;

vector<vector<ll>> A;
vector<pair<ll, pair<ll, ll>>> e;
ll n, x, y, k;
vector<ll> distX, distY, app1, app2;
vector<ll> type, xypath;
// void debug(){
//     for (ll i=0; i<n; i++){
//         cout << app1[i] << " ";
//     }
//     cout << ln;
//     for (ll i=0; i<n; i++){
//         cout << app2[i] << " ";
//     }
//     cout << ln;
// }
void calcDist(ll u, ll p, ll depth, vector<ll> &depthWrite){
    // cout << u << endl;
    depthWrite[u]=depth;
    for (auto i:A[u]){
        ll v = e[i].ss.ff^e[i].ss.ss^u;
        if (v==p) continue;
        calcDist(v, u, depth+e[i].ff, depthWrite);
    }
}
void genDist(){
    distX.resize(n); distY.resize(n); app1.resize(n); app2.resize(n); type.assign(n, 0);
    // return;
    calcDist(x, x, 0, distX);
    calcDist(y, y, 0, distY);
    // return;
    for (ll i=0; i<n; i++){
        app1[i]=min(distX[i], distY[i]);
        app2[i]=max(distX[i], distY[i])-app1[i];
        if (app1[i]>=app2[i]) type[i]=2;
        if  (app1[i]*2+app2[i]==distX[y]) {type[i]=1; xypath.push_back(i);}
    }
    // debug();
}

ll case1(){
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
    que.push({0, x});
    que.push({0, y});
    vector<bool> vis(n);
    ll ck=k, ans=0;
    while(!que.empty()){
        auto cur = que.top();
        que.pop();
        if (vis[cur.ss]) continue;
        if (cur.ff>ck) break;
        ck-=cur.ff;
        ans++;
        vis[cur.ss]=1;
        for (auto i:A[cur.ss]){
            ll v = e[i].ss.ff^e[i].ss.ss^cur.ss;
            if (!vis[v]) que.push({cur.ff+e[i].ff, v});
        }
    }
    return ans;
}

ll case2(){
    ll ck=k;
    ll ans=0;
    vector<ll> usd(n);
    for (auto v:xypath){
        ck-=app1[v];
        ans++;
        usd[v]++;
    }
    if (ck>0){
        // cout << "Hap" << ln;
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q1, q2;
        // q1-type 0 & 1; q2-type 2
        for (ll i=0; i<n; i++){
            if (type[i]==0){
                q1.push({app1[i], i});
                q1.push({app2[i], i});
            }else if (type[i]==1){
                q1.push({app2[i], i});
            }else{
                q2.push({app1[i]+app2[i], i});
            }
        }
        while (!q2.empty() and ck>0){
            if (q1.size()>=2){
                pair<pair<ll, ll>, pair<ll, ll>> q1l2;
                q1l2.ff=q1.top(); q1.pop(); q1l2.ss=q1.top(); 
                if (q2.top().ff>=q1l2.ff.ff+q1l2.ss.ff and q2.top().ff<=ck){
                    q1.push(q1l2.ff);
                    usd[q2.top().ss]=2;
                    ans+=2;
                    ck-=q2.top().ff;
                    q2.pop();
                }else{
                    if (q1l2.ff.ff+q1l2.ss.ff<=ck){
                        usd[q1l2.ff.ss]++; usd[q1l2.ss.ss]++;
                        ans+=2;
                        ck-=q1l2.ff.ff+q1l2.ss.ff;
                        q1.pop();
                    }else{
                        q1.push(q1l2.ff);
                        break;
                    }
                }
            }else{
                if (ck>=q2.top().ff){
                    ck-=q2.top().ff;
                    ans+=2;
                    usd[q2.top().ss]=2;
                    q2.pop();
                }else{
                    break;
                }
            }
        }
        while (!q1.empty() and ck>0){
            if (q1.top().ff<=ck){
                ck-=q1.top().ff;
                ans++;
                usd[q1.top().ss]++;
                q1.pop();
            }else break;
        }
        ll mn = LLONG_MAX;
        for (ll i=0; i<n; i++){
            if (type[i]==2 and usd[i]==0){
                mn=min(mn, app1[i]);
            }
        }
        if (mn<=ck){
            ans++;
        }
        return ans;
    }else return 0;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n=N; x=X; y=Y; k=K;
    A.clear(); e.clear(); distX.clear(); distY.clear(); app1.clear(); app2.clear(); type.clear(); xypath.clear();
    A.resize(n); e.resize(n-1);
    for (ll i=0; i<n-1; i++){
        e[i]={W[i], {U[i], V[i]}};
        A[U[i]].push_back(i);
        A[V[i]].push_back(i);
    }
    // return 0;
    genDist();
    // return 0;
    ll res=max(case2(), case1());
    return (int)res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 40340 KB Output is correct
2 Correct 92 ms 46540 KB Output is correct
3 Correct 50 ms 5180 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '90'
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '90'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '90'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 428 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '30', found: '26'
14 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '90'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '90'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '90'
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '90'
8 Halted 0 ms 0 KB -