Submission #1078809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078809		PoPularPlusPlus	Closing Time (IOI23_closing)	C++17	9 / 100	111 ms	25424 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){
    int ans = 2;
    vector<pair<int,ll>> adj[n];
    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]));
    }

    int dis1[n] , dis2[n];
    memset(dis1,-1,sizeof dis1);
    memset(dis2,-1,sizeof dis2);

    queue<int> q;
    q.push(x);
    dis1[x] = 0;
    while(q.size()){
        int node = q.front();
        q.pop();
        for(auto it : adj[node]){
            if(dis1[it.vf] == -1){
                dis1[it.vf] = dis1[node] + it.vs;
                q.push(it.vf);
            }
        }
    }


    dis2[y] = 0;
    q.push(y);

    while(q.size()){
        int node = q.front();
        q.pop();
        for(auto it : adj[node]){
            if(dis2[it.vf] == -1){
                dis2[it.vf] = dis2[node] + it.vs;
                q.push(it.vf);
            }
        }
    }

    bool visx[n] , visy[n];

    for(int i = 0; i < (1 << n); i++){
        int res = 0;
        ll rem = k;
        memset(visx,0,sizeof visx);
        memset(visy,0,sizeof visy);

        if(((1 << x) & i)){
            visx[x] = 0;
            q.push(x);
            while(q.size()){
                int node = q.front();
                q.pop();
                for(auto it : adj[node]){
                    if(!visx[it.vf]){
                        if((i & (1 << it.vf))){
                            visx[it.vf] = 1;
                            q.push(it.vf);
                        }
                    }
                }
            }
        }

        if(((1 << y) & i)){
            visy[x] = 0;
            q.push(x);
            while(q.size()){
                int node = q.front();
                q.pop();
                for(auto it : adj[node]){
                    if(!visy[it.vf]){
                        if((i & (1 << it.vf))){
                            visy[it.vf] = 1;
                            q.push(it.vf);
                        }
                    }
                }
            }
        }

        vector<int> v;
        for(int j = 0; j < n; j++){
            if((i & (1 << j))){
                if(visx[j] && visy[j]){
                    res++;
                    rem -= min(dis1[j] , dis2[j]);
                    v.pb(max(dis1[j] , dis2[j]) - min(dis2[j] , dis1[j]));
                }
                else if(visx[j]){
                    rem -= dis1[j];
                    res++;
                }
                else if(visy[j]){
                    rem -= dis2[j];
                    res++;
                }
            }
        }

        if(rem >= 0){
            sort(all(v));
            for(int i : v){
                if(rem - i >= 0){
                    res++;
                    rem -= i;
                }
            }

            ans = max(ans , res);
        }
    }

    return ans;
}

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