Submission #954814

#	Time	Username	Problem	Language	Result	Execution time	Memory
954814		Lobo	Closing Time (IOI23_closing)	C++17	29 / 100	223 ms	73580 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int inf = 1e18+10;
vector<int> path, line;
vector<pair<int,int>> g[maxn];
int n, dist[2][maxn], inl[maxn];

void dfsline(int u, int ant, int last) {
    path.pb(u);
    if(u == last) line = path;
    for(auto V : g[u]) {
        int v = V.fr;
        int w = V.sc;
        if(v == ant) continue;
        dfsline(v,u,last);
    }
    path.pop_back();
}

void dfsdist(int u, int ant, int id) {
    for(auto V : g[u]) {
        int v = V.fr;
        int w = V.sc;
        if(v == ant) continue;
        dist[id][v] = dist[id][u]+w;
        dfsdist(v,u,id);
    }
}

void dfsverts(int u, int ant, vector<int> &verts) {
    verts.pb(u);
    for(auto V : g[u]) {
        int v = V.fr;
        if(v == ant or inl[v] == 1) continue;
        dfsverts(v,u,verts);
    }
}


int32_t max_score(int32_t N, int32_t X, int32_t Y, long long k,
              vector<int32_t> U, vector<int32_t> V, vector<int32_t> W)
{
    n = N;
    line.clear();
    path.clear();
    for(int i = 0; i <= n; i++) {
        g[i].clear();
        inl[i] = 0;
        dist[0][i] = dist[1][i] = 0;
    }
    for(int i = 0; i < n-1; i++) {
        g[U[i]].pb(mp(V[i],W[i]));
        g[V[i]].pb(mp(U[i],W[i]));
    }

    dfsline(X,-1,Y);
    dfsdist(X,-1,0);
    dfsdist(Y,-1,1);

    for(auto x : line) {
        inl[x] = 1;
    }

    vector<vector<int>> dp2;
    vector<vector<int>> dp1;
    for(int j = 0; j < (int) line.size(); j++) {
        int rt = line[j];
        vector<int> verts;
        dfsverts(rt,-1,verts);

        // cout << rt << " " << verts.size() << endl;

        vector<int> dists;
        for(auto v : verts) {
            dists.pb(min(dist[0][v],dist[1][v]));
        }

        sort(all(dists));
        dp1.pb({});
        dp1[j].resize(2 * (int) verts.size()+1,inf);
        dp1[j][0] = 0;
        for(int i = 1; i <= (int) dists.size(); i++) {
            dp1[j][i] = dp1[j][i-1]+dists[i-1];
        }

        int delta = abs(dist[0][rt]-dist[1][rt]);

        dp2.pb({});
        dp2[j].resize(2 * (int) verts.size()+1,inf);
        dp2[j][0] = 0;

        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

        for(int i = 1; i <= 2*verts.size(); i++) {
            while(pq.size() && 2*pq.top().sc < i) pq.pop();

            if(pq.size()) dp2[j][i] = min(dp1[j][i],pq.top().fr+i*delta);
            else dp2[j][i] = dp1[j][i];

            if(i <= (int) verts.size()) pq.push(mp(dp1[j][i]-i*delta,i));

            // cout << "  " << i << " " << dp2[j][i] << " " << dp1[j][i] << endl;
        }
    }

    int ans1,ans2;
    //ninguem tem 2
    {
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> dps;
        for(int r = 0; r < line.size(); r++) {
            dps.push(mp(dp1[r][1]-dp1[r][0],mp(r,0)));
        }
        ans1 = 0;
        int curk = 0;
        while(dps.size()) {
            int delta = dps.top().fr;
            int r = dps.top().sc.fr;
            int i = dps.top().sc.sc;
            dps.pop();

            if(curk+delta <= k) {
                ans1++;
                curk+= delta;
                i++;
                if(i+1 < (int)dp1[r].size()) {
                    dps.push(mp(dp1[r][i+1]-dp1[r][i],mp(r,i)));
                }
            }
        }
    }

    // podem usar os 2, mas vai ate o meio
    {
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> dps;
        ans2 = 0;
        int curk = 0;
        for(int r = 0; r < line.size(); r++) {
            if(inl[r] == 1) {
                ans2++;
                curk+= dp2[r][1];
                dps.push(mp(dp2[r][2]-dp2[r][1],mp(r,1)));
            }
            else {
                dps.push(mp(dp2[r][1]-dp2[r][0],mp(r,0)));
            }
        }
        if(curk > k) {
            ans2 = 0;
        }
        while(dps.size()) {
            int delta = dps.top().fr;
            int r = dps.top().sc.fr;
            int i = dps.top().sc.sc;
            dps.pop();

            if(curk+delta <= k) {
                ans2++;
                curk+= delta;
                i++;
                if(i+1 < (int)dp2[r].size()) {
                    dps.push(mp(dp2[r][i+1]-dp2[r][i],mp(r,i)));
                }
            }
        }
    }
    return max(ans1,ans2);
    // int ans = 0;
    // int curk = 0;
    // while(dps.size()) {
    //     int delta = dps.top().fr;
    //     int r = dps.top().sc.fr;
    //     int i = dps.top().sc.sc;
    //     dps.pop();

    //     if(curk+delta <= k) {
    //         ans++;
    //         curk+= delta;
    //         i++;
    //         if(i+1 < (int)dp2[r].size()) {
    //             dps.push(mp(dp2[r][i+1]-dp2[r][i],mp(r,i)));
    //         }
    //     }
    // }

    // return ans;
}

Compilation message (stderr)

closing.cpp: In function 'void dfsline(long long int, long long int, long long int)':
closing.cpp:21:13: warning: unused variable 'w' [-Wunused-variable]
   21 |         int w = V.sc;
      |             ^
closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:102:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i = 1; i <= 2*verts.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
closing.cpp:118:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int r = 0; r < line.size(); r++) {
      |                        ~~^~~~~~~~~~~~~
closing.cpp:145:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for(int r = 0; r < line.size(); r++) {
      |                        ~~^~~~~~~~~~~~~

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