Submission #914310

#	Time	Username	Problem	Language	Result	Execution time	Memory
914310		Ludissey	Closing Time (IOI23_closing)	C++17	0 / 100	1051 ms	33484 KiB

closing

#include <bits/stdc++.h>
#include "closing.h"

using namespace std;
#define int long long
#define sz(a){ return (int)a.size(); }

const int INF=1e9;
vector<vector<pair<int,int>>> edges;
vector<int> dstX;
vector<int> dstY;

signed max_score(signed N, signed rootX, signed rootY, long long K, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W){
    vector<pair<int,int>> singl;
    vector<pair<int,int>> doubl;
    edges.clear();
    dstX.clear();
    edges.resize(N);
    dstX.resize(N);
    dstY.resize(N);
    singl.resize(N);
    doubl.resize(N);

    for (int i = 0; i < N-1; i++)
    {
        edges[V[i]].push_back({U[i], W[i]});
        edges[U[i]].push_back({V[i], W[i]});
    }
    vector<bool> visited(N);
    queue<pair<int,int>> queue;
    queue.push({rootX,0});
    while(!queue.empty()){
        int x=queue.front().first,w=queue.front().second; queue.pop();
        if(visited[x]) continue;
        visited[x]=true;
        dstX[x]=w;
        for (auto u: edges[x]) queue.push({u.first, u.second+w});
    }
    visited.clear();
    visited.resize(N);
    queue.push({rootY,0});
    while(!queue.empty()){
        int x=queue.front().first,w=queue.front().second; queue.pop();
        if(visited[x]) continue;
        visited[x]=true;
        dstY[x]=w;
        for (auto u: edges[x]) queue.push({u.first, u.second+w});
    }

    for (int i = 0; i < N; i++) singl[i]={min(dstY[i], dstX[i]),i};
    for (int i = 0; i < N; i++) doubl[i]={max(dstY[i],dstX[i]), i};

    int res=K;
    int sum=0;
    while(!singl.empty()){
        sort(singl.begin(),singl.end()); //  sort both
        sort(doubl.begin(),doubl.end());
        if(singl.size()==1||(res-(singl[0].first+singl[1].first)<0&&(doubl.empty()||(res-doubl[0].first)<0))){ 
            if(res-singl[0].first>=0) sum++;
            break; 
        }
        if(doubl.empty() || singl[0].first+singl[1].first<doubl[0].first){
            res-=singl[0].first+singl[1].first;
            int a=-1,b=-1;
            if(!doubl.empty()) {
                for (int i = 0; i < doubl.size(); i++)
                {
                    if(doubl[i].second==singl[0].second||doubl[i].second==singl[1].second) { 
                        a=i;
                        swap(a,b);
                    }
                }
            }
            if(b!=-1){
                singl.push_back({max(dstY[doubl[b].second], dstX[doubl[b].second]),doubl[b].second});
                doubl.erase(doubl.begin()+b); 
                if(b<a) a--;
                if(a!=-1){
                    singl.push_back({max(dstY[doubl[a].second], dstX[doubl[a].second]),doubl[a].second});
                    doubl.erase(doubl.begin()+a); 
                }
            }
            cerr<<singl[0].second << " " << singl[1].second << "- used\n";
            singl.erase(singl.begin());
            singl.erase(singl.begin());
        }else{
            res-=doubl[0].first;
            for (int i = 0; i < singl.size(); i++)
            {
                if(singl[i].second==doubl[0].second) { singl.erase(singl.begin()+i); break; }
            }
            cerr<<doubl[0].second << "- double used\n";
            doubl.erase(doubl.begin());
        }
        sum+=2;
    }
    
    return (int)sum;
}

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:66:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 for (int i = 0; i < doubl.size(); i++)
      |                                 ~~^~~~~~~~~~~~~~
closing.cpp:88:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for (int i = 0; i < singl.size(); i++)
      |                             ~~^~~~~~~~~~~~~~

• 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