제출 #1059281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059281		ZeroCool	Fire (BOI24_fire)	C++14	35 / 100	364 ms	54808 KiB

Main

#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 = 3000;
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?

*/

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();
	m = cmp.size();
	int mx[m + 1] = {0};
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

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){
      |           ^

• Subtask 1: 14 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 21 / 21
• Subtask 6: 0 / 26