| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1059286 |
2024-08-14T20:26:09 Z |
ZeroCool |
Fire (BOI24_fire) |
C++14 |
|
9 ms |
16220 KB |
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 1e6 + 20;
const int K = 300;
const int LOG = 30;
/*
Bidikland can be represneted like a circle with a lot of of smaller circles inside it. The bigest circle represent the border, and the smaller represent the municipalities.
No two circles can interesect but the can be contained within eachother. Lets defne the territory of municipality as their circle with the smaller circles contained inside it removed (see drawing for reference)
On the edge of any two mmunicipalities there are pay tolls, each toll costs exactly one Bidikdollar. One day Bidik realized tha the machines at all of the tolls are broken and he needed to fix them.
He hired Viktors company (con world) to send men to fix them. This is how to process of fixing goes: A mechanic starts from a municipality without any municipalities within it, he moves through the municipalities and needs to end at another municipality with no municipalities within it(the path he takes must be a simple path), on this trip he fixes all the tolls he passes but also has to pay them, so the cost of the trip is the number of tolls passed. What is minimal cost Bidik has to spend on tolls in order to fix all of them?
*/
int mx[N];
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
int n, m;
cin>>n>>m;
vector<ar<int, 2>> v;
int s[n], e[n];
set<int>ss = {0, m};
for(int i= 0;i <n ;i++){
cin>>s[i]>>e[i];
ss.insert(s[i]);
ss.insert(e[i]);
}
map<int,int> cmp;
for(auto u: ss)cmp[u] = cmp.size();
for(int i = 0;i <n;i++){
s[i] = cmp[s[i]], e[i] = cmp[e[i]];
if(s[i] > e[i])mx[s[i]] = m, v.push_back({s[i], e[i]});
mx[s[i]] = max(s[i], e[i]);
}
for(int i =1 ;i <= m;i++)mx[i] = max(mx[i], mx[i - 1]);
if(v.empty()){
cout<<-1;
return 0;
}
int ans = INF;
for(auto [a, b]: v){
int cnt = 1;
int u = b;
while(u < a){
if(mx[u] <= u)break;
u = mx[u];
++cnt;
}
if(u >= a)ans = min(ans, cnt);
}
if(ans >= INF)ans = -1;
cout<<ans;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:51:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for(auto [a, b]: v){
| ^
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Runtime error |
8 ms |
16220 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Runtime error |
8 ms |
16220 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Runtime error |
8 ms |
16220 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Runtime error |
9 ms |
16220 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
4 ms |
8028 KB |
Output is correct |
| 5 |
Correct |
0 ms |
440 KB |
Output is correct |
| 6 |
Runtime error |
9 ms |
16220 KB |
Execution killed with signal 11 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
344 KB |
Output is correct |
| 8 |
Runtime error |
8 ms |
16220 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
