Submission #1078396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078396		Lobo	Closing Time (IOI23_closing)	C++17	75 / 100	1068 ms	55840 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 10;
const int inf1 = 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxn = 2e5+10;

vector<int> line;
int wline;
int n, distx[maxn], disty[maxn], isline[maxn];
vector<pair<int,int>> g[maxn];
int makeline(int u, int ant, int final) {
    line.pb(u);
    if(u == final) {
        return 1;
    }

    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        if(makeline(v,u,final) == 1) {
            wline+= w;
            return 1;
        }
    }
    line.pop_back();
    return 0;
}

void makedistx(int u, int ant, int dis) {
    distx[u] = dis;
    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        makedistx(v,u,dis+w);
    }
}

void makedisty(int u, int ant, int dis) {
    disty[u] = dis;
    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        makedisty(v,u,dis+w);
    }
}

int32_t max_score(int32_t N, int32_t X, int32_t Y, long long K,
              std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W)
{
    

    line.clear();
    wline = 0;
    n = N;
    for(int i = 0; i < N; i++) {
        isline[i] = distx[i] = disty[i] = 0;
        g[i].clear();
    }
    for(int i = 0; i < U.size(); i++) {
        int u = U[i];
        int v = V[i];
        int w = W[i];
        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }
    makeline(X,-1,Y);
    // line[0] = X
    // line[line.size()-1] = Y
    for(auto x : line) isline[x] = 1;
    makedistx(X,-1,0);
    makedisty(Y,-1,0);

    int mx,my;
    for(int i = 0; i+1 < line.size(); i++) {
        if(distx[line[i+1]] > disty[line[i+1]]) {
            mx = line[i];
            my = line[i+1];
            break;
        }
    }


    int ans = 0;
    {
        
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
        int curk = 0;
        vector<int> atvx(n,0), atvy(n,0);
        atvx[X] = 1;
        atvy[Y] = 1;

        for(int u = 0; u < n; u++) {
            curk+= max(atvx[u]*distx[u],atvy[u]*disty[u]);
        }

        for(auto V : g[X]) {
            int v = V.fr;
            if(atvx[v] == 0 and v != my) {
                pq.push(mp(distx[v],mp(v,0)));
            }
        }
        for(auto V : g[Y]) {
            int v = V.fr;
            if(atvy[v] == 0 and v != mx) {
                pq.push(mp(disty[v],mp(v,1)));
            }
        }

        while(pq.size()) {
            int tp = pq.top().sc.sc;
            int u = pq.top().sc.fr;
            pq.pop();
            if(tp == 0) {
                if(curk+distx[u] <= K) {
                    atvx[u] = 1;
                    curk+= distx[u];
                    for(auto V : g[u]) {
                        int v = V.fr;
                        if(atvx[v] == 0 and v != my) {
                            pq.push(mp(distx[v],mp(v,0)));
                        }
                    }
                }
            }
            else {
                if(curk+disty[u] <= K) {
                    atvy[u] = 1;
                    curk+= disty[u];
                    for(auto V : g[u]) {
                        int v = V.fr;
                        if(atvy[v] == 0 and v != mx) {
                            pq.push(mp(disty[v],mp(v,1)));
                        }
                    }
                }
            }
        }

        if(curk <= K) {
            int qtd = 0;
            for(int i = 0; i < n; i++) {
                qtd+= atvx[i];
                qtd+= atvy[i];
            }

            ans = max(ans,qtd);
        }



    }

    {
        // os X vai ate mx e Y vai ate my, e continua dai

        vector<vector<int>> dpqtd(n), dpqtd1(n);
        for(auto r : line) {
            priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
            pq.push(mp(min(distx[r],disty[r]),r));
            dpqtd[r].pb(0);
            // cout << r << endl;
            while(pq.size()) {
                int u = pq.top().sc;
                pq.pop();
                dpqtd[r].pb(dpqtd[r].back()+min(distx[u],disty[u]));
                // cout << " " << u << " " << dpqtd[r].size() << " " << dpqtd[r].back() << endl;
                for(auto V : g[u]) {
                    int v = V.fr;
                    if(isline[v] == 0 and min(distx[u],disty[u]) < min(distx[v],disty[v])) {
                        pq.push(mp(min(distx[v],disty[v]),v));
                    }
                }
            }

            int subsize = (int) dpqtd[r].size()-1;
            dpqtd1[r].resize(2*subsize+1,inf);
            // for(int i = 0; i <= subsize; i++) {
            //     for(int j = 0; j <= i; j++) {
            //         dpqtd1[r][i+j] = min(dpqtd1[r][i+j],dpqtd[r][i]+j*(max(distx[r],disty[r])-min(distx[r],disty[r])));
            //     }
            // }

            int i = 0;
            for(int ij = 0; ij <= 2*subsize; ij++) {
                while(i+1 <= ij and i+1 <= subsize and ((ij-i) > i or 
                      dpqtd[r][i]+(ij-i)*(max(distx[r],disty[r])-min(distx[r],disty[r])) > dpqtd[r][i+1]+(ij-i-1)*(max(distx[r],disty[r])-min(distx[r],disty[r])))) {
                    i++;
                }
                dpqtd1[r][ij] = dpqtd[r][i]+(ij-i)*(max(distx[r],disty[r])-min(distx[r],disty[r]));
                // cout << ij << " - " << i << endl;
            }


            for(int i = 0; i < dpqtd1[r].size(); i++) {
                // cout << "   " << i << " " << dpqtd1[r][i] << " " << subsize << endl;
            }
        }

        vector<int> dp;
        dp.pb(0);

        for(auto r : line) {
            vector<int> newdp(dp.size()+dpqtd1[r].size()-1,inf);
            for(int i = 0; i < dp.size(); i++) {
                for(int j = 1; j < dpqtd1[r].size(); j++) {
                    newdp[i+j] = min(newdp[i+j],dp[i]+dpqtd1[r][j]);
                }
            }
            dp = newdp;
        }

        for(int i = 0; i < dp.size(); i++) {
            if(dp[i] <= K) {
                ans = max(ans,i);
            }
        }
    }


    return (int32_t) ans;
}

Compilation message (stderr)

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:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < U.size(); i++) {
      |                    ~~^~~~~~~~~~
closing.cpp:84:24: 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]
   84 |     for(int i = 0; i+1 < line.size(); i++) {
      |                    ~~~~^~~~~~~~~~~~~
closing.cpp:204:30: 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]
  204 |             for(int i = 0; i < dpqtd1[r].size(); i++) {
      |                            ~~^~~~~~~~~~~~~~~~~~
closing.cpp:214:30: 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]
  214 |             for(int i = 0; i < dp.size(); i++) {
      |                            ~~^~~~~~~~~~~
closing.cpp:215:34: 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]
  215 |                 for(int j = 1; j < dpqtd1[r].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~~~~
closing.cpp:222: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]
  222 |         for(int i = 0; i < dp.size(); i++) {
      |                        ~~^~~~~~~~~~~
closing.cpp:129:41: warning: 'my' may be used uninitialized in this function [-Wmaybe-uninitialized]
  129 |                         if(atvx[v] == 0 and v != my) {
closing.cpp:141:41: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |                         if(atvy[v] == 0 and v != mx) {

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