| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 939347 | WanWan | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
#define int long long
const int MAXN = 3005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
vector<pi>adj[MAXN];
int par[MAXN];
int dep[MAXN];
void dfs(int x, int p){
par[x]=p;
for(auto v:adj[x])if(v.first!=p){
dep[v.first]=dep[x]+1;
dfs(v.first,x);
}
}
int dd[2][MAXN];
void bfs(int src, int xx){
queue<int> qu;
memset(dd[xx],-1,sizeof dd[xx]);
dd[xx][src]=0;
qu.push(src);
while(qu.size()){
int c=qu.front();
qu.pop();
for(auto v:adj[c]){
if(dd[xx][v.first] == -1 || dd[xx][v.first] > dd[xx][c]+v.second){
dd[xx][v.first]=dd[xx][c]+v.second;
qu.push(v.first);
}
}
}
}
map<int,int>cst;
int mnsum[MAXN],mxsum[MAXN];
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)
{
for(int i=0;i<n;i++){
adj[i].clear();
}
for(int i=0;i<n-1;i++){
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
}
dfs(1,-1);
vector<int> v1,v2;
int x=X,y=Y;
while(x!=y){
if(dep[x]>dep[y]){
v1.push_back(x);
x=par[x];
} else{
v2.push_back(y);
y=par[y];
}
}
unordered_set<int> path;
reverse(v2.begin(),v2.end());
vector<int> vec;
for(auto e:v1)vec.push_back(e);
vec.push_back(x);
for(auto e:v2)vec.push_back(e);
for(auto e:vec)path.insert(e);
int ans=2;
// 1. calc if there's 0 intersection--just greedily choose the cheapest node
bfs(X,0);
bfs(Y,1);
{
vector<int> vs;
for(int i=0;i<n;i++)vs.push_back(dd[0][i]);
for(int i=0;i<n;i++)vs.push_back(dd[1][i]);
sort(vs.begin(),vs.end());
int cst=0;
int cc=0;
for(auto x:vs){
cst+=x;
++cc;
if(cst<=K){
ans=max(ans,cc);
} else{
break;
}
}
}
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> one; //{cost,index,min/max}
priority_queue<pi,vector<pi>,greater<pi>> both;
// 2. if there's at least 1 intersection, it'll happen on the path
for(int k=0;k<n;k++){
if(path.find(k) != path.end()){
} else{
both.push({max(dd[0][k],dd[1][k]),k});
one.push({min(dd[0][k],dd[1][k]),k,0});
}
}
set<pi>doneone;
set<int>doneboth;
int cost=0;
int cnt=0;
while(true){
// try taking 1 only
//cst[cost]=cnt;
while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
if(one.size()){
cst[cnt+1]=cost+one.top()[0];
cst[cnt+1]=min(cst[cnt+1],oo);
//if(cost+one.top()[0]<=K)ans=max(ans,cnt+1);
}
int c1=oo,c2=oo;
if(one.size()){
c1=0;
array<int,3> cur=one.top();
c1+=cur[0];
one.pop();
while(one.size() && doneone.find({one.top()[1],one.top()[2]}) != doneone.end())one.pop();
if(one.size())c1+=one.top()[0];
else c1=oo;
one.push(cur);
}
while(both.size() && doneboth.find(both.top().second) != doneboth.end())both.pop();
if(both.size()){
c2=both.top().first;
}
if(c2==oo && c1==oo)break;
if(c2<c1){ // we should take the smaller one of the both
assert(both.size());
pi cur=both.top();
cnt++;
cost += min(dd[0][cur.second],dd[1][cur.second]);
one.push({abs(dd[0][cur.second]-dd[1][cur.second]),cur.second,1});
doneone.insert({cur.second,0});
both.pop();
} else{
array<int,3>cur=one.top();
one.pop();
cnt++;
cost+=cur[0];
if(cur[2] == 0){ // push max
one.push({max(dd[0][cur[1]],dd[1][cur[1]])-cur[0],cur[1],1});
doneboth.insert(cur[1]);
}
}
if(cst.find(cnt) == cst.end())cst[cnt]=cost;
else cst[cnt]=min(cst[cnt],cost);
cst[cnt]=min(cst[cnt],oo);
}
for(int i=0;i<vec.size();i++){
mnsum[i]=mnsum[i-1]+min(dd[1][vec[k]],dd[0][vec[k]]);
mxsum[i]=mxsum[i-1]+max(dd[0][vec[k]],dd[1][vec[k]]);
}
for(int i=0;i<vec.size();i++){
for(int j=i;j<vec.size();j++){
int cost = 0;
int cnt=0;
int cnt=vec.size()+(j-i+1);
int cost=mnsum[i-1];
cost += mxsum[j];
cost -= mxsum[i];
cost += mnsum[vec.size()-1];
cost -= mnsum[j];
/*
for(int k=0;k<vec.size();k++){
if(k<i){
cost+=min(dd[1][vec[k]],dd[0][vec[k]]);
++cnt;
}
else if(k<=j){
cost+=max(dd[0][vec[k]],dd[1][vec[k]]);
cnt+=2;
}
else {
cost+=min(dd[1][vec[k]],dd[0][vec[k]]);
++cnt;
}
}*/
if(cost>K)continue;
ans=max(ans,cnt);
for(auto x:cst){
if(cost+x.second<=K){
ans=max(ans,cnt+x.first);
}
}
}
}
cst.clear();
return ans;
}