#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
int32_t main() {
char p, q;
int s, t, k, n; cin >> k >> n;
ll ans = 0;
unordered_map<int,int> bruh;
unordered_map<int,int> sus;
vector<int> bridgeplaces;
vector<pair<int, int>> housework;
if (k == 2) {
return 0;
}
ll ahead = 0;
for (int i=0;i<n;i++) {
cin >> p >> s >> q >> t;
if (t > s) {
swap(t, s);
}
if (p == q) {
ans += abs(s - t);
continue;
}
ahead++;
housework.push_back(make_pair(t, s));
if (bruh.find(s) == bruh.end()) {
bruh[s] = 1;
if (sus.find(s) == sus.end()) {
bridgeplaces.push_back(s);
}
} else {
bruh[s]++;
}
if (sus.find(t) == sus.end()) {
sus[t] = 1;
if (bruh.find(t) == bruh.end()) {
bridgeplaces.push_back(t);
}
} else {
sus[t]++;
}
}
sort(bridgeplaces.begin(), bridgeplaces.end());
for (pair<int,int> i: housework) {
ans += i.first + i.second + 1;
}
ll curans = ans;
ll prev = 0;
ll visitednum = 0;
for (int i=0;i<bridgeplaces.size();i++) {
curans += 2 * (bridgeplaces[i] - prev) * (visitednum - ahead);
//cout << visitednum << ' ' << ahead << ' ' << bridgeplaces[i] << ' ' << curans << '\n';
if (bruh.find(bridgeplaces[i]) != bruh.end()) {
visitednum += bruh[bridgeplaces[i]];
}
if (sus.find(bridgeplaces[i]) != sus.end()) {
ahead -= sus[bridgeplaces[i]];
}
ans = min(ans, curans);
prev = bridgeplaces[i];
}
cout << ans;
}
Compilation message
bridge.cpp: In function 'int32_t main()':
bridge.cpp:56:19: 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]
56 | for (int i=0;i<bridgeplaces.size();i++) {
| ~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
444 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
448 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
22 ms |
3244 KB |
Output is correct |
13 |
Correct |
98 ms |
14640 KB |
Output is correct |
14 |
Correct |
33 ms |
4336 KB |
Output is correct |
15 |
Correct |
55 ms |
8596 KB |
Output is correct |
16 |
Correct |
37 ms |
3788 KB |
Output is correct |
17 |
Correct |
93 ms |
14668 KB |
Output is correct |
18 |
Correct |
58 ms |
14384 KB |
Output is correct |
19 |
Correct |
107 ms |
14792 KB |
Output is correct |
20 |
Correct |
46 ms |
3780 KB |
Output is correct |
21 |
Correct |
83 ms |
14616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |