Submission #224213

#	Time	Username	Problem	Language	Result	Execution time	Memory
224213		mieszko11b	Treatment Project (JOI20_treatment)	C++14	35 / 100	999 ms	524292 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;

const ll INF = 1e18;

#define X first
#define Y second

int n, m;
vector<ii> P;
vector<ii> G[1500007];
ll dist[1500007];

int add_point(int x, int y) {
	P.emplace_back(x, y);
	return P.size() - 1;
}

void add_edges(vector<int> &F, vector<int> &T) {
	if(F.empty() || T.empty())
		return ;
		
	for(int f : F)
		for(int t : T)
			if(P[t].X >= P[f].X && P[t].Y <= P[f].Y)
				G[f].emplace_back(t, 0);
}

ll dijkstra() {
	ll res = INF;
	
	set<pll> S;
	
	for(int i = 0 ; i < P.size() ; i++) {
		if(P[i].Y - P[i].X == 0) {
			dist[i] = 0;
			S.insert({0, i});
		} else
			dist[i] = INF;
	}
	
	while(!S.empty()) {
		auto p = *(S.begin());
		S.erase(S.begin());
		
		for(auto p2 : G[p.Y]) {
			if(dist[p2.X] > p.X + p2.Y) {
				S.erase({dist[p2.X], p2.X});
				dist[p2.X] = p.X + p2.Y;
				S.insert({dist[p2.X], p2.X});
			}
		}
	}
	
	for(int i = 0 ; i < P.size() ; i++)
		if(P[i].Y - P[i].X == n * 2)
			res = min(res, dist[i]);
	
	return res;
}

int main() {
	scanf("%d%d", &n, &m);
	vector<int> F, T;
	for(int i = 0 ; i < m ; i++) {
		int t, l, r, c;
		scanf("%d%d%d%d", &t, &l, &r, &c);
		l--;
		F.push_back(add_point(t - r, t + r));
		T.push_back(add_point(t - l, t + l));
		G[T.back()].emplace_back(F.back(), c);
	}
	
	sort(F.begin(), F.end());
	sort(T.begin(), T.end());
	
	add_edges(F, T);
	ll hlp;
	printf("%lld\n", (hlp = dijkstra()) == INF ? -1 : hlp);
	
	return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'll dijkstra()':
treatment.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < P.size() ; i++) {
                  ~~^~~~~~~~~~
treatment.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < P.size() ; i++)
                  ~~^~~~~~~~~~
treatment.cpp: In function 'int main()':
treatment.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &t, &l, &r, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61