#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 10;
const int inf1 = 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxn = 2e5+10;
vector<int> line;
int wline;
int n, distx[maxn], disty[maxn], isline[maxn];
vector<pair<int,int>> g[maxn];
int makeline(int u, int ant, int final) {
line.pb(u);
if(u == final) {
return 1;
}
for(auto V : g[u]) if(V.fr != ant) {
int v = V.fr;
int w = V.sc;
if(makeline(v,u,final) == 1) {
wline+= w;
return 1;
}
}
line.pop_back();
return 0;
}
void makedistx(int u, int ant, int dis) {
distx[u] = dis;
for(auto V : g[u]) if(V.fr != ant) {
int v = V.fr;
int w = V.sc;
makedistx(v,u,dis+w);
}
}
void makedisty(int u, int ant, int dis) {
disty[u] = dis;
for(auto V : g[u]) if(V.fr != ant) {
int v = V.fr;
int w = V.sc;
makedisty(v,u,dis+w);
}
}
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)
{
line.clear();
wline = 0;
n = N;
for(int i = 0; i < N; i++) {
isline[i] = distx[i] = disty[i] = 0;
g[i].clear();
}
for(int i = 0; i < U.size(); i++) {
int u = U[i];
int v = V[i];
int w = W[i];
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
makeline(X,-1,Y);
// line[0] = X
// line[line.size()-1] = Y
for(auto x : line) isline[x] = 1;
makedistx(X,-1,0);
makedisty(Y,-1,0);
int ans = 0;
{
// nenhum chega no outro
for(int rx = 0; rx < line.size(); rx++) {
for(int ly = line.size()-1; ly >= 0; ly--) {
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
int curk = 0;
vector<int> atvx(n,0), atvy(n,0);
for(int i = 0; i <= rx; i++) {
atvx[line[i]] = 1;
}
for(int i = ly; i < line.size(); i++) {
atvy[line[i]] = 1;
}
for(int u = 0; u < n; u++) {
curk+= max(atvx[u]*distx[u],atvy[u]*disty[u]);
}
for(auto V : g[X]) {
int v = V.fr;
if(isline[v] == 0) {
pq.push(mp(distx[v],mp(v,0)));
}
}
for(auto V : g[Y]) {
int v = V.fr;
if(isline[v] == 0) {
pq.push(mp(disty[v],mp(v,1)));
}
}
while(pq.size()) {
int tp = pq.top().sc.sc;
int u = pq.top().sc.fr;
pq.pop();
if(tp == 0) {
if(curk+distx[u] <= K) {
atvx[u] = 1;
curk+= distx[u];
for(auto V : g[u]) {
int v = V.fr;
if(atvx[v] == 0) {
pq.push(mp(distx[v],mp(v,0)));
}
}
}
}
else {
if(curk+disty[u] <= K) {
atvy[u] = 1;
curk+= disty[u];
for(auto V : g[u]) {
int v = V.fr;
if(atvy[v] == 0) {
pq.push(mp(disty[v],mp(v,1)));
}
}
}
}
}
if(curk <= K) {
int qtd = 0;
for(int i = 0; i < n; i++) {
qtd+= atvx[i];
qtd+= atvy[i];
}
ans = max(ans,qtd);
}
}
}
}
{
// os dois chegam um no outro
vector<int> atv(n,0);
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
int curk = 0;
for(auto v : line) {
atv[v] = 2;
curk+= max(distx[v],disty[v]);
}
for(auto V : g[X]) {
int v = V.fr;
if(atv[v] == 0) pq.push(mp(distx[v],mp(v,0)));
}
for(auto V : g[Y]) {
int v = V.fr;
if(atv[v] == 0) pq.push(mp(disty[v],mp(v,1)));
}
int qtd = 2;
while(pq.size()) {
int tp = pq.top().sc.sc;
int u = pq.top().sc.fr;
pq.pop();
if(tp == 0) {
if(curk+distx[u] <= K) {
atv[u] = 1;
curk+= distx[u];
for(auto V : g[u]) {
int v = V.fr;
if(atv[v] == 0) {
pq.push(mp(distx[v],mp(v,0)));
}
}
}
}
else {
if(curk+disty[u] <= K) {
atv[u] = 1;
curk+= disty[u];
for(auto V : g[u]) {
int v = V.fr;
if(atv[v] == 0) {
pq.push(mp(disty[v],mp(v,1)));
}
}
}
}
if(curk <= K) {
ans = max(ans, 2*(int)line.size() + qtd + min(qtd,(K-curk)/wline));
}
}
}
return (int32_t) ans;
}
Compilation message
closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 0; i < U.size(); i++) {
| ~~^~~~~~~~~~
closing.cpp:86:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int rx = 0; rx < line.size(); rx++) {
| ~~~^~~~~~~~~~~~~
closing.cpp:94:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = ly; i < line.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
36588 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
4956 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
