oj.uz

Submission #224221

# Submission time Handle Problem Language Result Execution time Memory
224221 2020-04-17T14:00:14 Z mieszko11b Treatment Project (JOI20_treatment) C++14
100 / 100
 1320 ms 178876 KB 
#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[3000007];
ll dist[3000007];

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

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 172048 KB Output is correct
2 Correct 628 ms 175300 KB Output is correct
3 Correct 657 ms 143672 KB Output is correct
4 Correct 666 ms 143676 KB Output is correct
5 Correct 476 ms 129360 KB Output is correct
6 Correct 527 ms 147600 KB Output is correct
7 Correct 641 ms 166592 KB Output is correct
8 Correct 337 ms 129872 KB Output is correct
9 Correct 388 ms 147516 KB Output is correct
10 Correct 483 ms 167872 KB Output is correct
11 Correct 834 ms 161580 KB Output is correct
12 Correct 790 ms 158276 KB Output is correct
13 Correct 927 ms 174828 KB Output is correct
14 Correct 928 ms 175052 KB Output is correct
15 Correct 824 ms 174004 KB Output is correct
16 Correct 804 ms 173884 KB Output is correct
17 Correct 834 ms 173116 KB Output is correct
18 Correct 821 ms 158760 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70784 KB Output is correct
2 Correct 42 ms 70776 KB Output is correct
3 Correct 43 ms 70776 KB Output is correct
4 Correct 43 ms 70784 KB Output is correct
5 Correct 44 ms 70776 KB Output is correct
6 Correct 42 ms 70784 KB Output is correct
7 Correct 45 ms 70784 KB Output is correct
8 Correct 43 ms 70776 KB Output is correct
9 Correct 43 ms 70784 KB Output is correct
10 Correct 46 ms 70780 KB Output is correct
11 Correct 44 ms 70776 KB Output is correct
12 Correct 42 ms 70776 KB Output is correct
13 Correct 43 ms 70784 KB Output is correct
14 Correct 44 ms 70776 KB Output is correct
15 Correct 43 ms 70776 KB Output is correct
16 Correct 42 ms 70776 KB Output is correct
17 Correct 43 ms 70776 KB Output is correct
18 Correct 44 ms 70784 KB Output is correct
19 Correct 45 ms 70776 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70784 KB Output is correct
2 Correct 42 ms 70776 KB Output is correct
3 Correct 43 ms 70776 KB Output is correct
4 Correct 43 ms 70784 KB Output is correct
5 Correct 44 ms 70776 KB Output is correct
6 Correct 42 ms 70784 KB Output is correct
7 Correct 45 ms 70784 KB Output is correct
8 Correct 43 ms 70776 KB Output is correct
9 Correct 43 ms 70784 KB Output is correct
10 Correct 46 ms 70780 KB Output is correct
11 Correct 44 ms 70776 KB Output is correct
12 Correct 42 ms 70776 KB Output is correct
13 Correct 43 ms 70784 KB Output is correct
14 Correct 44 ms 70776 KB Output is correct
15 Correct 43 ms 70776 KB Output is correct
16 Correct 42 ms 70776 KB Output is correct
17 Correct 43 ms 70776 KB Output is correct
18 Correct 44 ms 70784 KB Output is correct
19 Correct 45 ms 70776 KB Output is correct
20 Correct 69 ms 74140 KB Output is correct
21 Correct 66 ms 74224 KB Output is correct
22 Correct 73 ms 74732 KB Output is correct
23 Correct 69 ms 74732 KB Output is correct
24 Correct 81 ms 74860 KB Output is correct
25 Correct 77 ms 74732 KB Output is correct
26 Correct 76 ms 74732 KB Output is correct
27 Correct 67 ms 74732 KB Output is correct
28 Correct 82 ms 74780 KB Output is correct
29 Correct 77 ms 74732 KB Output is correct
30 Correct 64 ms 74732 KB Output is correct
31 Correct 63 ms 74732 KB Output is correct
32 Correct 75 ms 74860 KB Output is correct
33 Correct 68 ms 74476 KB Output is correct
34 Correct 71 ms 74732 KB Output is correct
35 Correct 75 ms 74860 KB Output is correct
36 Correct 69 ms 74352 KB Output is correct
37 Correct 71 ms 74732 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 172048 KB Output is correct
2 Correct 628 ms 175300 KB Output is correct
3 Correct 657 ms 143672 KB Output is correct
4 Correct 666 ms 143676 KB Output is correct
5 Correct 476 ms 129360 KB Output is correct
6 Correct 527 ms 147600 KB Output is correct
7 Correct 641 ms 166592 KB Output is correct
8 Correct 337 ms 129872 KB Output is correct
9 Correct 388 ms 147516 KB Output is correct
10 Correct 483 ms 167872 KB Output is correct
11 Correct 834 ms 161580 KB Output is correct
12 Correct 790 ms 158276 KB Output is correct
13 Correct 927 ms 174828 KB Output is correct
14 Correct 928 ms 175052 KB Output is correct
15 Correct 824 ms 174004 KB Output is correct
16 Correct 804 ms 173884 KB Output is correct
17 Correct 834 ms 173116 KB Output is correct
18 Correct 821 ms 158760 KB Output is correct
19 Correct 45 ms 70784 KB Output is correct
20 Correct 42 ms 70776 KB Output is correct
21 Correct 43 ms 70776 KB Output is correct
22 Correct 43 ms 70784 KB Output is correct
23 Correct 44 ms 70776 KB Output is correct
24 Correct 42 ms 70784 KB Output is correct
25 Correct 45 ms 70784 KB Output is correct
26 Correct 43 ms 70776 KB Output is correct
27 Correct 43 ms 70784 KB Output is correct
28 Correct 46 ms 70780 KB Output is correct
29 Correct 44 ms 70776 KB Output is correct
30 Correct 42 ms 70776 KB Output is correct
31 Correct 43 ms 70784 KB Output is correct
32 Correct 44 ms 70776 KB Output is correct
33 Correct 43 ms 70776 KB Output is correct
34 Correct 42 ms 70776 KB Output is correct
35 Correct 43 ms 70776 KB Output is correct
36 Correct 44 ms 70784 KB Output is correct
37 Correct 45 ms 70776 KB Output is correct
38 Correct 69 ms 74140 KB Output is correct
39 Correct 66 ms 74224 KB Output is correct
40 Correct 73 ms 74732 KB Output is correct
41 Correct 69 ms 74732 KB Output is correct
42 Correct 81 ms 74860 KB Output is correct
43 Correct 77 ms 74732 KB Output is correct
44 Correct 76 ms 74732 KB Output is correct
45 Correct 67 ms 74732 KB Output is correct
46 Correct 82 ms 74780 KB Output is correct
47 Correct 77 ms 74732 KB Output is correct
48 Correct 64 ms 74732 KB Output is correct
49 Correct 63 ms 74732 KB Output is correct
50 Correct 75 ms 74860 KB Output is correct
51 Correct 68 ms 74476 KB Output is correct
52 Correct 71 ms 74732 KB Output is correct
53 Correct 75 ms 74860 KB Output is correct
54 Correct 69 ms 74352 KB Output is correct
55 Correct 71 ms 74732 KB Output is correct
56 Correct 847 ms 159036 KB Output is correct
57 Correct 844 ms 163460 KB Output is correct
58 Correct 776 ms 174396 KB Output is correct
59 Correct 802 ms 174792 KB Output is correct
60 Correct 912 ms 175296 KB Output is correct
61 Correct 770 ms 174536 KB Output is correct
62 Correct 867 ms 158824 KB Output is correct
63 Correct 720 ms 176448 KB Output is correct
64 Correct 663 ms 174924 KB Output is correct
65 Correct 752 ms 175644 KB Output is correct
66 Correct 820 ms 175296 KB Output is correct
67 Correct 1238 ms 174592 KB Output is correct
68 Correct 1160 ms 175152 KB Output is correct
69 Correct 958 ms 175932 KB Output is correct
70 Correct 1260 ms 174388 KB Output is correct
71 Correct 1162 ms 174268 KB Output is correct
72 Correct 912 ms 174780 KB Output is correct
73 Correct 1238 ms 174920 KB Output is correct
74 Correct 631 ms 174536 KB Output is correct
75 Correct 571 ms 174784 KB Output is correct
76 Correct 866 ms 164924 KB Output is correct
77 Correct 1131 ms 178876 KB Output is correct
78 Correct 961 ms 174400 KB Output is correct
79 Correct 1310 ms 173688 KB Output is correct
80 Correct 857 ms 173748 KB Output is correct
81 Correct 665 ms 173500 KB Output is correct
82 Correct 891 ms 172860 KB Output is correct
83 Correct 1014 ms 172836 KB Output is correct
84 Correct 1320 ms 172860 KB Output is correct
85 Correct 995 ms 173888 KB Output is correct
86 Correct 865 ms 174116 KB Output is correct
87 Correct 1010 ms 173900 KB Output is correct
88 Correct 882 ms 174888 KB Output is correct
89 Correct 892 ms 173892 KB Output is correct
90 Correct 1156 ms 175932 KB Output is correct
91 Correct 1115 ms 173976 KB Output is correct
92 Correct 956 ms 173628 KB Output is correct
93 Correct 1289 ms 173872 KB Output is correct
94 Correct 904 ms 170544 KB Output is correct
95 Correct 1192 ms 173500 KB Output is correct
96 Correct 1186 ms 175756 KB Output is correct
97 Correct 1193 ms 176872 KB Output is correct
98 Correct 1282 ms 176960 KB Output is correct
99 Correct 1218 ms 176956 KB Output is correct
100 Correct 939 ms 163008 KB Output is correct
101 Correct 1234 ms 176584 KB Output is correct
102 Correct 977 ms 164540 KB Output is correct
103 Correct 934 ms 174012 KB Output is correct