Submission #1079996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079996		PoPularPlusPlus	Closing Time (IOI23_closing)	C++17	0 / 100	1059 ms	34116 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vf first
#define vs second
 
int max_score(int n, int x, int y, ll k,vector<int> u, vector<int> v, vector<int> w){

    vector<pair<int,ll>> adj[n + 1];
    for(int i = 0; i < n-1; i++){
        adj[u[i]].pb(mp(v[i] , w[i]));
        adj[v[i]].pb(mp(u[i] , w[i]));
    }

    ll dis[n] , path[n] , dis1[n];
    memset(dis,-1,sizeof dis);
    memset(path , -1 , sizeof path);
    memset(dis1, -1 , sizeof dis1);
    queue<int> q;
    q.push(x);
    dis[x] = 0;
    path[x] = 0;
    while(q.size()){
        int node = q.front();
        q.pop();
        for(auto i : adj[node]){
            if(dis[i.vf] == -1){
                dis[i.vf] = dis[node] + i.vs;
                path[i.vf] = path[node] + 1;
                q.push(i.vf);
            }
        }
    }

    bool vis[n];
    memset(vis,0,sizeof vis);
    vis[y] = 1;
    ll cur = y;
    vector<int> path_w;
    path_w.pb(y);
    while(cur != x){
        for(auto i : adj[cur]){
            if(path[i.vf] == path[cur] - 1){
                cur = i.vf;
                vis[i.vf] = 1;
                path_w.pb(i.vf);
                break;
            }
        }
    }

    dis1[y] = 0;
    q.push(y);
    while(q.size()){
        int node = q.front();
        q.pop();
        for(auto i : adj[node]){
            if(dis1[i.vf] == -1){
                dis1[i.vf] = dis1[node] + i.vs;
                path[i.vf] = path[node] + 1;
                q.push(i.vf);
            }
        }
    }

   /* for(int i = 0; i < n; i++){
        cout << dis[i] << ' ' << dis1[i] << '\n';
    }*/

    int weight[n];
    priority_queue<pair<ll,int>> pq;

    for(int i = 0; i < n; i++){
        if(vis[i] == 0 && dis[i] < dis1[i]){
            pq.push(mp(dis[i],i));
        }
    }

    int pos = 0;
    while(pq.size()){
        //cout << "former " << ' ' << pq.top().vs << '\n';
        weight[pos++] = pq.top().vs;
        pq.pop();
    }

    int xx = pos;

    while(path_w.size()){
        weight[pos++] = path_w.back();
        path_w.pop_back();
    }

    for(int i = 0; i < n; i++){
        if(vis[i] == 0 && dis[i] > dis1[i]){
            pq.push(mp(dis1[i] , i));
        }
    }

    int yy = pos -1; 

    vector<int> rev;
    while(pq.size()){
        rev.pb(pq.top().vs);
        pq.pop();
    }

    while(rev.size()){
        //cout << "later " << pq.top().vs << '\n';
        weight[pos++] = rev.back();
        rev.pop_back();
    }

    for(int i = 0; i < n; i++){
        cout << weight[i] << ' ';
    }
    cout << '\n';

    x = xx;
    y = yy;

    cur = 0;
    int ans = 0;
    ll cur_w[n];
    for(int i = x; i >= 0; i--){
        for(int j = y; j < n; j++){
            memset(cur_w,0,sizeof cur_w);
            ll rem = k;
            ll cur = 0;
            for(int tp = x; tp >= i; tp--){
                rem -= dis[weight[tp]];
                //cout << "dis " << dis[weight[tp]] << ' ';
                cur_w[tp] = dis[weight[tp]];
            }
 
            cur = 0;
            for(int tp = y; tp <= j; tp++){
                rem -= dis1[weight[tp]];
                //cout << "dis1 " << dis1[weight[tp]] << ' ';
                cur_w[tp] = dis1[weight[tp]];
            }

            //cout << i << ' ' << j << ' ' << rem << endl;
 
            if(rem >= 0){
                int res = (x - i) + (j - y) + 2;
               // cout << res << ' ';
                int left = x + 1 , right = y - 1;
                ll cur_l = dis[weight[left]] , cur_r = dis1[weight[right]];
                while(rem >= 0 && (left < n || right >= 0)){
                    //cout << rem << ' ' << left << ' ' << right << endl;
                    if(right < 0 || (left < n && cur_l - cur_w[left] < cur_r - cur_w[right])){
                        if(rem - (max(0LL,cur_l - cur_w[left])) >= 0){
                            rem -= (max(0LL,cur_l - cur_w[left]));
                            cur_w[left] += (max(0LL,cur_l - cur_w[left]));
                            res++;
                            left++;
                            if(left < n)cur_l = dis[weight[left]];
                        }
                        else break;
                    }
                    else {
                        if(rem - max(0LL, cur_r - cur_w[right]) >= 0){
                            rem -= max(0LL, cur_r - cur_w[right]);
                            cur_w[right] += max(0LL, cur_r - cur_w[right]);
                            res++;
                            right--;
                            if(right >= 0)cur_r = dis1[weight[right]];
                        }
                        else break;
                    }
                }
               // cout << i << ' ' << j << ' ' << res << ' ' << rem << ' ' << left << ' ' << right << '\n';
               // cout << i << ' ' << j << ' ' << res << ' ' << left << ' ' << right << "\n";
                ans = max(ans , res);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:132:16: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  132 |             ll cur = 0;
      |                ^~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 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