#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> father, father_dis;
bitset<100001> vis, vis2;
vector<int> components, c2;
vector<int> dis;
void new_comp(int node, int c, int N){
vis2 = bitset<100001>(0);
father.assign(N, -1);
father_dis.assign(N, 0);
dis.assign(N, 0);
// queue<pair<int, int>> q;
vector<pair<int, int>> q;
q.emplace_back(make_pair(node, 0));
int r = 0;
int c1 = 0;
while(c1 != q.size()){
pair<int, int> cur = q[c1++];
r++;
vis[cur.first] = 1;
dis[cur.first] = cur.second;
for(pair<int, int> e : adj[cur.first]){
if(!vis[e.first])
q.emplace_back(make_pair(e.first, cur.second + e.second));
}
}
if(r == 1)
return;
q.clear();
int end = max_element(dis.begin(), dis.end()) - dis.begin();
dis.assign(N, 0);
q.emplace_back(make_pair(end, 0));
c1 = 0;
while(!q.empty()){
pair<int, int> cur = q[c1++];
vis2[cur.first] = 1;
dis[cur.first] = cur.second;
for(pair<int, int> e : adj[cur.first]){
if(!vis2[e.first]){
father[e.first] = cur.first;
father_dis[e.first] = e.second;
q.emplace_back(make_pair(e.first, cur.second + e.second));
}
}
}
auto it = max_element(dis.begin(), dis.end());
end = it - dis.begin();
int pops = father[end];
int cur_dis = INT_MAX;
int travel = 0;
while(pops != -1){
travel += father_dis[end];
cur_dis = min(cur_dis, max(travel, *it - travel));
end = pops;
pops = father[end];
}
c2.push_back(*it);
components.push_back(cur_dis);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
for(int i = 0; i < M; i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
int c = 0;
for(int i = 0; i < N; i++){
if(!vis[i]){
new_comp(i, c++, N);
}
}
sort(components.rbegin(), components.rend());
int max_d = *max_element(c2.begin(), c2.end());
if(c == 1)
return components[0];
if(c == 2)
return max(max_d, components[0] + components[1] + L);
return max({max_d, components[0] + components[1] + L, components[1] + components[2] + 2*L});
}
Compilation message
dreaming.cpp: In function 'void new_comp(int, int, int)':
dreaming.cpp:21:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | while(c1 != q.size()){
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
16868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
16868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
16868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
11884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
16868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
16868 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
