Submission #861572

#	Time	Username	Problem	Language	Result	Execution time	Memory
861572		hocky	Closing Time (IOI23_closing)	C++17	43 / 100	77 ms	38484 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i = a;i < b;i++)
#define trav(nx, v) for(auto &nx : v)
#define all(a) begin(a), end(a)
#define sz(v) (int) v.size()

int n;
typedef array<LL, 4> CostNodeFrom;
CostNodeFrom plain = {-1,-1,-1,-1};
multiset<CostNodeFrom> prim;
const int LIM = 200000;
vector <PLL> edge[LIM + 5];
bool isInside[LIM + 5][2];
LL curans[LIM + 5];
CostNodeFrom cheap[LIM + 5][2];
ostream& operator<<(ostream &os, CostNodeFrom c) {
	os <<"(" << c[0] << ", " << c[1] << ", " << c[2] << ", " << c[3] <<")";
	return os;
}
 

void updateCheap(int node, LL val, bool isY) {
	//~ cout << "Updating " << endl;
	cheap[node][isY] = plain;
	if(cheap[node][!isY][1] != -1) {
		prim.erase(prim.find(cheap[node][!isY]));
		curans[node] += val;
		cheap[node][!isY][0] = max(0LL, cheap[node][!isY][3] - curans[node]);
		prim.insert(cheap[node][!isY]);
	} else {
		curans[node] += val;
	}
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
	K *= 2;
	n = N;
	rep(i,0,N) {
		edge[i].clear();
		isInside[i][0] = isInside[i][1] = 0;
		curans[i] = 0;
		cheap[i][0] = cheap[i][1] = plain;
	}
	//~ cout << "Here " << U[0] << " " << V[0] << ""  << W[0] << endl;
	prim.clear();
	rep(i,0,N - 1){
		auto tmp = 2LL * W[i];
		if(tmp > K) continue;
		//~ cout << U[i] << " " << V[i] << endl;
		edge[U[i]].emplace_back(V[i], tmp);
		edge[V[i]].emplace_back(U[i], tmp);
		
	}
	isInside[X][0] = 1;
	isInside[Y][1] = 1;
	LL ans = 2;
	trav(tmp, edge[X]){
		CostNodeFrom nx = {tmp.se, tmp.fi, 0, tmp.se};
		prim.insert(nx);
		cheap[tmp.fi][0] = nx;
	}
	trav(tmp, edge[Y]) {
		CostNodeFrom nx = {tmp.se, tmp.fi, 1, tmp.se};
		prim.insert(nx);
		cheap[tmp.fi][1] = nx;
	}
	while(sz(prim)){
		auto currentTop = *prim.begin();
		//~ cout << "here K = " << K << " relaxing node " << currentTop[1] << " with cost " << currentTop[0] << " from node " << currentTop[2] << endl;
		prim.erase(prim.begin());
		if(K < currentTop[0]) break;
		updateCheap(currentTop[1], currentTop[0], currentTop[2]);
		trav(cur, edge[currentTop[1]]){
			if(isInside[cur.fi][currentTop[2]]) continue;
			auto addCost = max(currentTop[3] + cur.se - curans[cur.fi], 0LL);
			CostNodeFrom nxCheap = {addCost, cur.fi, currentTop[2], currentTop[3] + cur.se};
			cheap[cur.fi][currentTop[2]] = nxCheap;
			prim.insert(nxCheap);
		}
		K -= currentTop[0];
		ans++;
		isInside[currentTop[1]][currentTop[2]] = 1;
	}
	//~ rep(i,0,n){
		//~ cout << curans[i] << " ";
	//~ }
	//~ cout << endl;
    return ans;
}

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