| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 861571 | hocky | Dynamic Diameter (CEOI19_diameter) | 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;
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;
}