Submission #224220

#	Time	Username	Problem	Language	Result	Execution time	Memory
224220		mieszko11b	Treatment Project (JOI20_treatment)	C++14	35 / 100	499 ms	216636 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];

bool comp_point(int a, int b) {
	return P[a] < P[b];
}

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

int cnt = 0;

void add_edges(vector<int> &F, vector<int> &T) {
	if(F.empty() || T.empty())
		return ;
		
	vector<int> all;
	
	int i = 0, j = 0;
	while(i < F.size() || j < T.size()) {
		if(i < F.size() && (j == T.size() || P[F[i]] < P[T[j]])) {
			all.push_back(F[i]);
			i++;
		} else {
			all.push_back(T[j]);
			j++;
		}
	}
	
	int xmid = P[all[(all.size() - 1) / 2]].X;
	
	//~ for(int x : F) cout << P[x].X << "," << P[x].Y << "  "; cout << endl;
	//~ for(int x : T) cout << P[x].X << "," << P[x].Y << "  "; cout << endl;
	//~ cout << xmid << endl << endl;
	
	vector<int> F1, F2;
	vector<int> T1, T2;
	
	vector<ii> M;
	
	for(int i : F) {
		if(P[i].X <= xmid) {
			if(P[i].X < xmid)
				F1.push_back(i);
			int hlp = add_point(xmid, P[i].Y);
			M.push_back({P[i].Y, hlp});
			G[i].emplace_back(hlp, 0);
		} else
			F2.push_back(i);
	}
	
	for(int i : T) {
		if(P[i].X >= xmid) {
			if(P[i].X > xmid)
				T2.push_back(i);
			int hlp = add_point(xmid, P[i].Y);
			M.push_back({P[i].Y, hlp});
			G[hlp].emplace_back(i, 0);
		} else
			T1.push_back(i);
	}
	
	sort(M.begin(), M.end(), greater<ii>());
	
	for(int i = 0 ; i + 1 < M.size() ; i++) {
		G[M[i].Y].emplace_back(M[i + 1].Y, 0);
		if(M[i].X == M[i + 1].X)
			G[M[i + 1].Y].emplace_back(M[i].Y, 0);
	}
	
	add_edges(F1, T1);
	add_edges(F2, T2);
}

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(), comp_point);
	sort(T.begin(), T.end(), comp_point);
	
	add_edges(F, T);
	ll hlp;
	printf("%lld\n", (hlp = dijkstra()) == INF ? -1 : hlp);
	
	return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'void add_edges(std::vector<int>&, std::vector<int>&)':
treatment.cpp:37:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < F.size() || j < T.size()) {
        ~~^~~~~~~~~~
treatment.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < F.size() || j < T.size()) {
                        ~~^~~~~~~~~~
treatment.cpp:38:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i < F.size() && (j == T.size() || P[F[i]] < P[T[j]])) {
      ~~^~~~~~~~~~
treatment.cpp:38:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i < F.size() && (j == T.size() || P[F[i]] < P[T[j]])) {
                       ~~^~~~~~~~~~~
treatment.cpp:82:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i + 1 < M.size() ; i++) {
                  ~~~~~~^~~~~~~~~~
treatment.cpp: In function 'll dijkstra()':
treatment.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < P.size() ; i++) {
                  ~~^~~~~~~~~~
treatment.cpp:118: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:126: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:130: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