#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<17), inf = (1<<30);
int n, m, lprice;
struct edge{
int ver, cost;
edge(){
ver = -1;
cost = 0;
}
edge(int _ver, int _cost){
ver = _ver;
cost = _cost;
}
bool operator<(const edge &other) const{
return cost > other.cost;
}
};
struct diamgr{
int s, f;
int cost, sum1, sum2;
diamgr(){
/*mid =*/ s = f = -1;
cost = sum1 = sum2 = -1;
}
diamgr(int _s, int _f, int _cost, int _sum1, int _sum2){
s = _s;
f = _f;
//mid = _mid;
cost = _cost;
sum1 = _sum1;
sum2 = _sum2;
}
};
vector <edge> v[maxn];
bool used[maxn];
bool checkver[maxn];
int parsum[maxn], parsum1[maxn], parsum2[maxn];
int anscost;
int d[maxn];
int par[maxn], costpar[maxn];
inline void init_vectors(int *a, int *b, int *t){
for (int i = 0; i < m; ++i){
v[a[i]].push_back(edge(b[i], t[i]));
v[b[i]].push_back(edge(a[i], t[i]));
//cerr << a[i] << " " << b[i] << " " << t[i] << endl;
}
}
void check_component(int ver){
checkver[ver] = 1;
for (auto nb: v[ver]){
//cerr << "ver: " << ver << " nb: " << nb.ver << "\n";
if (!checkver[nb.ver])
check_component(nb.ver);
}
}
int Dijkstra(int beg){
memset(used, 0, sizeof(used));
memset(par, -1, sizeof(par));
memset(costpar, 0, sizeof(costpar));
used[beg] = 1;
checkver[beg] = 1;
for (int i = 0; i < n; ++i)
d[i] = inf;
d[beg] = 0;
costpar[beg] = 0;
par[beg] = -1;
priority_queue<edge> q;
q.push(edge(beg, 0));
int lastpopped = -1;
while (!q.empty()){
edge cur = q.top();
q.pop();
lastpopped = cur.ver;
if (cur.cost <= d[cur.ver]){
used[cur.ver] = 1;
checkver[cur.ver] = 1;
for (int i = 0; i < (int)v[cur.ver].size(); ++i){
edge nb = v[cur.ver][i];
if (cur.cost + nb.cost < d[nb.ver]){
par[nb.ver] = cur.ver;
costpar[nb.ver] = nb.cost;
d[nb.ver] = cur.cost + nb.cost;
nb.cost = d[nb.ver];
q.push(nb);
}
}
}
}
return lastpopped;
}
int init_parsums(int s, int f, int *parsum){
int cur = f, prev = -1;
int cnt = 1;
while (cur != -1){
parsum[cnt] = parsum[cnt - 1] + costpar[cur];
cur = par[cur];
cnt++;
}
return cnt;
}
pair<int, int> find_mindif(int n, int *parsum){
if (n == 1) return {0, 0};
if (n == 2) return {0, parsum[1]};
int sum1 = -(1<<30) + 10, sum2 = (1<<30) - 10;
for (int i = 0; i < n; ++i){
int cursum1 = parsum[i];
int cursum2 = parsum[n - 1] - parsum[i];
if (abs(cursum2 - cursum1) < abs(sum2 - sum1)){
sum1 = cursum1;
sum2 = cursum2;
}
}
return {sum1, sum2};
}
pair<int, int> find_gr_dim(int ver){
//cerr << "find_gr_dim ver: " << ver << "\n";
check_component(ver);
if (v[ver].size() == 0){
return {0, 0};
}
int s = Dijkstra(ver);
int f = Dijkstra(s);
//cerr << "Gr. diam: " << d[f] << endl;
memset(parsum, 0, sizeof(parsum));
int cntver = init_parsums(s, f, parsum);
pair<int, int> sums = find_mindif(cntver, parsum);
//cerr << "sums: " << sums.first << " " << sums.second << "\n";
return sums;
}
inline void subtask123(int *a, int *b, int *t){
init_vectors(a, b, t);
pair<int, int> info1, info2;
bool lamp = false;
for (int i = 0; i < n; ++i){
//cerr << "checkver[" << i << "] == " << checkver[i] << endl;
if (!checkver[i]){
if (!lamp){
info1 = find_gr_dim(i);
lamp = true;
}
else info2 = find_gr_dim(i);
}
}
int diam1 = info1.first + info1.second;
int diam2 = info2.first + info2.second;
int max1 = max(info1.first, info1.second);
int max2 = max (info2.first, info2.second);
anscost = max1 + max2 + lprice;
anscost = max(anscost, diam1);
anscost = max(anscost, diam2);
}
inline void solve(int *a, int *b, int *t){
init_vectors(a, b, t);
pair<int, int> info;
multiset<int> comp;
for (int i = 0; i < n; ++i)
if (!checkver[i]){
info = find_gr_dim(i);
int m1 = max(info.first, info.second);
int m2 = min(info.first, info.second);
comp.insert(m1);
int sum = m1 + m2;
anscost = max(anscost, sum);
}
int m1, m2, m3;
m1 = m2 = m3 = 0;
auto it = comp.end();
--it;
m1 = *it;
--it;
m2 = *it;
if (it == comp.begin()){
int sum = m1 + m2;
anscost = max(anscost, sum);
return;
}
--it;
m3 = *it;
int sum = m1 + m2 + lprice;
anscost = max(anscost, sum);
sum = m2 + m3 + lprice + lprice;
anscost = max(anscost, sum);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
m = M;
lprice = L;
//subtask1(A, B, T);
//subtask123(A, B, T);
solve(A, B, T);
return anscost;
}
/*cout << n1 << " " << n2 << "\n";
for (int i = 0; i < n1; ++i)
cout << parsum1[i] << " ";
cout << "\n";
for (int i = 0; i < n2; ++i)
cout << parsum2[i] << " ";
cout << "\n";*/
/*int find_deepest(int ver){
//cout << "ver " << ver << "\n";
used[ver] = true;
if (!used[v[ver][0].first])
return find_deepest(v[ver][0].first);
if (v[ver].size() > 1 && !used[v[ver][1].first])
return find_deepest(v[ver][1].first);
return ver;
}
inline void init_chain(int i, int &s, int &f){
//cout << "i: " << i << "\n";
used[i] = true;
if (v[i].size() == 0) s = i;
else s = find_deepest(v[i][0].first);
//cerr << "found one end\n";
if (v[i].size() <= 1) f = i;
else f = find_deepest(v[i][1].first);
//cerr << "found another end\n\n";
}
inline void find_chains(int &s1, int &f1, int &s2, int &f2){
s1 = f1 = s2 = f2 = -1;
for (int i = 0; i < n; ++i)
if (!used[i]){
if (s1 == -1) init_chain(i, s1, f1);
else init_chain(i, s2, f2);
}
}
int init_parsums(int s, int f, int *parsum){
int cur = s, prev = -1;
int cnt = 1;
while (cur != f){
for (pair<int, int> nb: v[cur])
if (nb.first != prev){
parsum[cnt] = parsum[cnt - 1] + nb.second;
prev = cur;
cur = nb.first;
break;
}
cnt++;
}
return cnt;
}
pair<int, int> find_mindif(int n, int *parsum){
if (n == 1) return {0, 0};
if (n == 2) return {0, parsum[1]};
int sum1 = -(1<<30) + 10, sum2 = (1<<30) - 10;
for (int i = 0; i < n; ++i){
int cursum1 = parsum[i];
int cursum2 = parsum[n - 1] - parsum[i];
if (abs(cursum2 - cursum1) < abs(sum2 - sum1)){
sum1 = cursum1;
sum2 = cursum2;
}
}
return {sum1, sum2};
}
inline void subtask1(int *a, int *b, int *t){
init_vectors(a, b, t);
int s1, f1, s2, f2;
find_chains(s1, f1, s2, f2);
int n1 = init_parsums(s1, f1, parsum1);
int n2 = init_parsums(s2, f2, parsum2);
pair<int, int> sums1, sums2;
sums1 = find_mindif(n1, parsum1);
sums2 = find_mindif(n2, parsum2);
//cout << sums1.first << " " << sums1.second << " " << sums2.first << " " << sums2.second << "\n";
int max1 = max(sums1.first, sums1.second);
int max2 = max(sums2.first, sums2.second);
anscost = max1 + max2 + lprice;
anscost = max(anscost, sums1.first + sums1.second);
anscost = max(anscost, sums2.first + sums2.second);
}
*/
Compilation message
dreaming.cpp: In function 'int init_parsums(int, int, int*)':
dreaming.cpp:103:18: warning: unused variable 'prev' [-Wunused-variable]
103 | int cur = f, prev = -1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
10832 KB |
Output is correct |
| 2 |
Correct |
42 ms |
10848 KB |
Output is correct |
| 3 |
Correct |
25 ms |
9652 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7004 KB |
Output is correct |
| 5 |
Correct |
6 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
10 ms |
7244 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
6232 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
10832 KB |
Output is correct |
| 2 |
Correct |
42 ms |
10848 KB |
Output is correct |
| 3 |
Correct |
25 ms |
9652 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7004 KB |
Output is correct |
| 5 |
Correct |
6 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
10 ms |
7244 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
6232 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1044 ms |
9368 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
10832 KB |
Output is correct |
| 2 |
Correct |
42 ms |
10848 KB |
Output is correct |
| 3 |
Correct |
25 ms |
9652 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7004 KB |
Output is correct |
| 5 |
Correct |
6 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
10 ms |
7244 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
6232 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
