Submission #230237

# Submission time Handle Problem Language Result Execution time Memory
230237 2020-05-09T09:35:11 Z onjo0127 None (JOI14_ho_t5) C++11
10 / 100
3000 ms 9572 KB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int _N = 100009;

struct line {
	int p, l, r;
};

long long ans;
int W, H, N, A[_N], B[_N], C[_N], D[_N], pa[_N], lc;
set<pii> S;
line L[_N];

int getx(vector<int> &S, int x) { return lower_bound(S.begin(), S.end(), x) - S.begin() + 1; }

int root(int x) {
	if(pa[x] == x) return x;
	return pa[x] = root(pa[x]);
}
void merg(int u, int v) {
	u = root(u); v = root(v);
	if(u != v) pa[u] = v;
}

void dnc_y(int s, int e, vector<int> &VL, vector<int> &HL) {
	if(VL.empty() || HL.empty()) return;
	vector<int> MV, NV, LH, RH;
	int m = s+e >> 1;
	for(auto& it: VL) {
		if(L[it].r < s || e < L[it].l) continue;
		if(L[it].l <= s && e <= L[it].r) MV.push_back(it);
		else NV.push_back(it);
	}
	for(auto& it: HL) {
		if(L[it].p <= m) LH.push_back(it);
		else RH.push_back(it);
	}
	if(s != e) {
		dnc_y(s, m, NV, LH);
		dnc_y(m+1, e, NV, RH);
	}
	if(MV.size()) {
		//ans += (ll)MV.size() * (ll)HL.size();
		for(auto& it: MV) merg(it, HL[0]);
		for(auto& it: HL) merg(it, HL[0]);
		for(auto& it: MV) for(auto& jt: HL) S.insert({it, jt});
	}
}

void dnc_x(int s, int e, vector<int> &VL, vector<int> &HL) {
	if(VL.empty() || HL.empty()) return;
	vector<int> LV, RV, NH, MH;
	int m = s+e >> 1;
	for(auto& it: VL) {
		if(L[it].p <= m) LV.push_back(it);
		else RV.push_back(it);
	}
	for(auto& it: HL) {
		if(L[it].r < s || e < L[it].l) continue;
		if(L[it].l <= s && e <= L[it].r) MH.push_back(it);
		else NH.push_back(it);
	}
	if(s != e) {
		dnc_x(s, m, LV, NH);
		dnc_x(m+1, e, RV, NH);
	}
	dnc_y(1, H, VL, MH);
}

int main() {
	vector<int> XS, YS;
	scanf("%d%d%d",&W,&H,&N);
	XS.push_back(0); XS.push_back(W);
	YS.push_back(0); YS.push_back(H);
	for(int i=0; i<N; i++) {
		scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
		XS.push_back(A[i]); XS.push_back(B[i]);
		YS.push_back(C[i]); YS.push_back(D[i]);
	}
	sort(XS.begin(), XS.end()); XS.resize(unique(XS.begin(), XS.end()) - XS.begin());
	sort(YS.begin(), YS.end()); YS.resize(unique(YS.begin(), YS.end()) - YS.begin());
	/*
	W = getx(XS, W); H = getx(YS, H);
	for(int i=0; i<N; i++) {
		A[i] = getx(XS, A[i]);
		B[i] = getx(YS, B[i]);
		C[i] = getx(XS, C[i]);
		D[i] = getx(YS, D[i]);
	}
	*/
	vector<int> VL, HL;
	L[++lc] = {0, 0, H}; VL.push_back(lc);
	L[++lc] = {W, 0, H}; VL.push_back(lc);
	L[++lc] = {0, 0, W}; HL.push_back(lc);
	L[++lc] = {H, 0, W}; HL.push_back(lc);
	for(int i=0; i<N; i++) {
		if(A[i] == C[i]) {
			L[++lc] = {A[i], B[i], D[i]};
			VL.push_back(lc);
		}
		if(B[i] == D[i]) {
			L[++lc] = {B[i], A[i], C[i]};
			HL.push_back(lc);
		}
	}
	for(int i=1; i<=lc; i++) pa[i] = i;
	ans = -N-4;
	//dnc_x(1, W, VL, HL);
	for(auto& it: VL) for(auto& jt: HL) {
		if(L[it].l <= L[jt].p && L[jt].p <= L[it].r && L[jt].l <= L[it].p && L[it].p <= L[jt].r) {
			merg(it, jt);
			++ans;
		}
	}
	for(int i=1; i<=lc; i++) if(root(i) == i) ++ans;
	ans += S.size();
	printf("%lld", ans);
	return 0;
}

//f = c-v+e

Compilation message

2014_ho_t5.cpp: In function 'void dnc_y(int, int, std::vector<int>&, std::vector<int>&)':
2014_ho_t5.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
2014_ho_t5.cpp: In function 'void dnc_x(int, int, std::vector<int>&, std::vector<int>&)':
2014_ho_t5.cpp:55:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&W,&H,&N);
  ~~~~~^~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 8 ms 384 KB Output is correct
22 Correct 7 ms 384 KB Output is correct
23 Correct 8 ms 384 KB Output is correct
24 Correct 9 ms 384 KB Output is correct
25 Correct 8 ms 384 KB Output is correct
26 Correct 7 ms 384 KB Output is correct
27 Correct 8 ms 384 KB Output is correct
28 Correct 8 ms 512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 154 ms 1280 KB Output is correct
6 Execution timed out 3089 ms 5100 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 271 ms 1284 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Execution timed out 3087 ms 9572 KB Time limit exceeded
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 8 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 8 ms 384 KB Output is correct
22 Correct 7 ms 384 KB Output is correct
23 Correct 8 ms 384 KB Output is correct
24 Correct 9 ms 384 KB Output is correct
25 Correct 8 ms 384 KB Output is correct
26 Correct 7 ms 384 KB Output is correct
27 Correct 8 ms 384 KB Output is correct
28 Correct 8 ms 512 KB Output is correct
29 Correct 7 ms 384 KB Output is correct
30 Correct 6 ms 384 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 7 ms 512 KB Output is correct
33 Correct 154 ms 1280 KB Output is correct
34 Execution timed out 3089 ms 5100 KB Time limit exceeded
35 Halted 0 ms 0 KB -