답안 #36944 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36944	2017-12-19T14:16:46 Z	cheater2k	Port Facility (JOI17_port_facility)	C++14	78 / 100	2216 ms	886516 KB

port_facility

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5; // TODO: fix

struct Node {
	int L; int R; int cnt;
	Node() { L = R = cnt = 0; }
} T[N * 20];

int pos[N * 2][2], segl[N * 2], segr[N * 2];
vector< pair<int,int> > G[N * 20];
bool color[N * 20]; int cnt; // for bipartite checking
bool vis[N * 20]; // for BFS
int n, peak, version;
pair<int,int> a[N];
vector<int> z;

#define mid ((l + r) >> 1)
int build(int l, int r) {
	if (l == r) {
		pos[l][1] = ++peak; // on
		T[peak].L = T[peak].R = peak; T[peak].cnt = 1;
		pos[l][0] = ++peak; // off
		T[peak].L = T[peak].R = peak;
		return peak; // currently off
	}
	int le = build(l, mid), ri = build(mid + 1, r);
	++peak; T[peak].L = le; T[peak].R = ri;
	return peak;
}

int upd(int v, int l, int r, int p, int val) {
	if (l > r || l > p || r < p) return v;
	if (l == r) return pos[p][val];
	int le = upd(T[v].L, l, mid, p, val);
	int ri = upd(T[v].R, mid + 1, r, p, val);
	++peak; T[peak].L = le; T[peak].R = ri;
	T[peak].cnt = T[T[peak].L].cnt + T[T[peak].R].cnt;
	//printf("new node: %d -> L = %d R = %d\n", peak, T[peak].L, T[peak].R);
	return peak;
}

void add(int cur, int v, int l, int r, int L, int R) {
	if (l > r || R < l || L > r) return;
	if (L <= l && r <= R) {
		// cur and v belong to different sides in the bipartite graph
		if (!T[v].cnt) return; // off
		G[cur].push_back(make_pair(1, v)); G[v].push_back(make_pair(1, cur));
		vis[v] = true;
		return;
	}
	add(cur, T[v].L, l, mid, L, R); add(cur, T[v].R, mid + 1, r, L, R);
}
#undef mid

void dfs(int u) {
	vis[u] = 1;
	for (auto e : G[u]) {
		int v = e.second, id = e.first;
		if (!vis[v]) {
			color[v] = (color[u] ^ id); dfs(v);
		} else if (vis[v] && color[v] != (color[u] ^ id)) {
			printf("0\n"); exit(0); // invalid
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i) {
		segl[a[i].first] = i;
		segr[a[i].second] = i;
		z.push_back(a[i].second);
	}
	sort(z.begin(), z.end());
	z.erase(unique(z.begin(), z.end()), z.end());
	version = build(1, n);

	for (int lef = 1; lef <= 2 * n; ++lef) {
		int del = segr[lef - 1];
		int plef = lower_bound(z.begin(), z.end(), lef) - z.begin() + 1;
		if (del) {
			// delete
			version = upd(version, 1, n, plef - 1, 0);
		}
		int cur = segl[lef];
		if (!cur) continue;
		int rig = a[cur].second;
		int prig = lower_bound(z.begin(), z.end(), rig) - z.begin() + 1;

		// add
		add(pos[prig][1], version, 1, n, plef, prig);
		// update
		version = upd(version, 1, n, prig, 1);
	}

	// BFS
	queue <int> qu;
	for (int i = 1; i <= peak; ++i) if (vis[i]) qu.push(i);
	while(!qu.empty()) {
		int u = qu.front(); qu.pop();
		if (T[T[u].L].cnt) {
			G[u].push_back(make_pair(0, T[u].L)); G[T[u].L].push_back(make_pair(0, u));
			if (!vis[T[u].L]) {
				qu.push(T[u].L);
				vis[T[u].L] = true;
			}
		}
		if (T[T[u].R].cnt) {
			G[u].push_back(make_pair(0, T[u].R)); G[T[u].R].push_back(make_pair(0, u));
			if (!vis[T[u].R]) {
				qu.push(T[u].R);
				vis[T[u].R] = true;
			}
		}
	}

	// check for bipartite graph
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= z.size(); ++i) {
		if (!vis[pos[i][1]]) {
			++cnt; color[pos[i][1]] = 0; dfs(pos[i][1]);
		}
	}
	int ans = 1;
	while(cnt-- > 0) ans = 2LL * ans % (int)(1e9 + 7);
	printf("%d\n", ans);
}

Compilation message

port_facility.cpp: In function 'int main()':
port_facility.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= z.size(); ++i) {
                    ^

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	216 ms	783436 KB	Output is correct
2	Correct	193 ms	783436 KB	Output is correct
3	Correct	173 ms	783436 KB	Output is correct
4	Correct	189 ms	783436 KB	Output is correct
5	Correct	169 ms	783436 KB	Output is correct
6	Correct	196 ms	783436 KB	Output is correct
7	Correct	193 ms	783436 KB	Output is correct
8	Correct	233 ms	783436 KB	Output is correct
9	Correct	163 ms	783436 KB	Output is correct
10	Correct	159 ms	783436 KB	Output is correct
11	Correct	186 ms	783436 KB	Output is correct
12	Correct	189 ms	783436 KB	Output is correct
13	Correct	213 ms	783436 KB	Output is correct
14	Correct	166 ms	783436 KB	Output is correct
15	Correct	196 ms	783436 KB	Output is correct
16	Correct	189 ms	783436 KB	Output is correct
17	Correct	216 ms	783436 KB	Output is correct
18	Correct	219 ms	783436 KB	Output is correct
19	Correct	179 ms	783436 KB	Output is correct
20	Correct	223 ms	783436 KB	Output is correct
21	Correct	176 ms	783436 KB	Output is correct
22	Correct	229 ms	783436 KB	Output is correct
23	Correct	206 ms	783436 KB	Output is correct
24	Correct	196 ms	783436 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	216 ms	783436 KB	Output is correct
2	Correct	193 ms	783436 KB	Output is correct
3	Correct	173 ms	783436 KB	Output is correct
4	Correct	189 ms	783436 KB	Output is correct
5	Correct	169 ms	783436 KB	Output is correct
6	Correct	196 ms	783436 KB	Output is correct
7	Correct	193 ms	783436 KB	Output is correct
8	Correct	233 ms	783436 KB	Output is correct
9	Correct	163 ms	783436 KB	Output is correct
10	Correct	159 ms	783436 KB	Output is correct
11	Correct	186 ms	783436 KB	Output is correct
12	Correct	189 ms	783436 KB	Output is correct
13	Correct	213 ms	783436 KB	Output is correct
14	Correct	166 ms	783436 KB	Output is correct
15	Correct	196 ms	783436 KB	Output is correct
16	Correct	189 ms	783436 KB	Output is correct
17	Correct	216 ms	783436 KB	Output is correct
18	Correct	219 ms	783436 KB	Output is correct
19	Correct	179 ms	783436 KB	Output is correct
20	Correct	223 ms	783436 KB	Output is correct
21	Correct	176 ms	783436 KB	Output is correct
22	Correct	229 ms	783436 KB	Output is correct
23	Correct	206 ms	783436 KB	Output is correct
24	Correct	196 ms	783436 KB	Output is correct
25	Correct	203 ms	783700 KB	Output is correct
26	Correct	206 ms	783700 KB	Output is correct
27	Correct	213 ms	783700 KB	Output is correct
28	Correct	179 ms	783700 KB	Output is correct
29	Correct	163 ms	783700 KB	Output is correct
30	Correct	186 ms	783700 KB	Output is correct
31	Correct	213 ms	783700 KB	Output is correct
32	Correct	229 ms	783700 KB	Output is correct
33	Correct	216 ms	783700 KB	Output is correct
34	Correct	206 ms	783700 KB	Output is correct
35	Correct	199 ms	783436 KB	Output is correct
36	Correct	173 ms	783436 KB	Output is correct
37	Correct	189 ms	783964 KB	Output is correct
38	Correct	226 ms	783964 KB	Output is correct
39	Correct	199 ms	783568 KB	Output is correct
40	Correct	236 ms	783436 KB	Output is correct
41	Correct	173 ms	783568 KB	Output is correct
42	Correct	159 ms	783568 KB	Output is correct
43	Correct	169 ms	783700 KB	Output is correct
44	Correct	206 ms	783700 KB	Output is correct

Subtask #3
56.0 / 56.0

#	결과	실행 시간	메모리	Grader output
1	Correct	216 ms	783436 KB	Output is correct
2	Correct	193 ms	783436 KB	Output is correct
3	Correct	173 ms	783436 KB	Output is correct
4	Correct	189 ms	783436 KB	Output is correct
5	Correct	169 ms	783436 KB	Output is correct
6	Correct	196 ms	783436 KB	Output is correct
7	Correct	193 ms	783436 KB	Output is correct
8	Correct	233 ms	783436 KB	Output is correct
9	Correct	163 ms	783436 KB	Output is correct
10	Correct	159 ms	783436 KB	Output is correct
11	Correct	186 ms	783436 KB	Output is correct
12	Correct	189 ms	783436 KB	Output is correct
13	Correct	213 ms	783436 KB	Output is correct
14	Correct	166 ms	783436 KB	Output is correct
15	Correct	196 ms	783436 KB	Output is correct
16	Correct	189 ms	783436 KB	Output is correct
17	Correct	216 ms	783436 KB	Output is correct
18	Correct	219 ms	783436 KB	Output is correct
19	Correct	179 ms	783436 KB	Output is correct
20	Correct	223 ms	783436 KB	Output is correct
21	Correct	176 ms	783436 KB	Output is correct
22	Correct	229 ms	783436 KB	Output is correct
23	Correct	206 ms	783436 KB	Output is correct
24	Correct	196 ms	783436 KB	Output is correct
25	Correct	203 ms	783700 KB	Output is correct
26	Correct	206 ms	783700 KB	Output is correct
27	Correct	213 ms	783700 KB	Output is correct
28	Correct	179 ms	783700 KB	Output is correct
29	Correct	163 ms	783700 KB	Output is correct
30	Correct	186 ms	783700 KB	Output is correct
31	Correct	213 ms	783700 KB	Output is correct
32	Correct	229 ms	783700 KB	Output is correct
33	Correct	216 ms	783700 KB	Output is correct
34	Correct	206 ms	783700 KB	Output is correct
35	Correct	199 ms	783436 KB	Output is correct
36	Correct	173 ms	783436 KB	Output is correct
37	Correct	189 ms	783964 KB	Output is correct
38	Correct	226 ms	783964 KB	Output is correct
39	Correct	199 ms	783568 KB	Output is correct
40	Correct	236 ms	783436 KB	Output is correct
41	Correct	173 ms	783568 KB	Output is correct
42	Correct	159 ms	783568 KB	Output is correct
43	Correct	169 ms	783700 KB	Output is correct
44	Correct	206 ms	783700 KB	Output is correct
45	Correct	633 ms	796944 KB	Output is correct
46	Correct	646 ms	798648 KB	Output is correct
47	Correct	566 ms	795764 KB	Output is correct
48	Correct	583 ms	798640 KB	Output is correct
49	Correct	589 ms	796412 KB	Output is correct
50	Correct	553 ms	797976 KB	Output is correct
51	Correct	563 ms	799052 KB	Output is correct
52	Correct	363 ms	784244 KB	Output is correct
53	Correct	326 ms	784244 KB	Output is correct
54	Correct	589 ms	816156 KB	Output is correct
55	Correct	603 ms	816156 KB	Output is correct
56	Correct	586 ms	815412 KB	Output is correct
57	Correct	403 ms	790980 KB	Output is correct
58	Correct	339 ms	784244 KB	Output is correct
59	Correct	416 ms	785040 KB	Output is correct
60	Correct	463 ms	789000 KB	Output is correct
61	Correct	546 ms	792168 KB	Output is correct
62	Correct	453 ms	790164 KB	Output is correct
63	Correct	453 ms	790864 KB	Output is correct
64	Correct	509 ms	793140 KB	Output is correct
65	Correct	2216 ms	886372 KB	Output is correct
66	Correct	2146 ms	886516 KB	Output is correct
67	Correct	506 ms	799624 KB	Output is correct
68	Correct	466 ms	799672 KB	Output is correct
69	Correct	513 ms	800864 KB	Output is correct
70	Correct	519 ms	800936 KB	Output is correct
71	Correct	403 ms	793316 KB	Output is correct
72	Correct	443 ms	793316 KB	Output is correct
73	Correct	403 ms	791848 KB	Output is correct
74	Correct	366 ms	791848 KB	Output is correct
75	Correct	479 ms	797692 KB	Output is correct
76	Correct	436 ms	797700 KB	Output is correct
77	Correct	446 ms	797700 KB	Output is correct
78	Correct	606 ms	798452 KB	Output is correct
79	Correct	599 ms	797196 KB	Output is correct

Subtask #4
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	216 ms	783436 KB	Output is correct
2	Correct	193 ms	783436 KB	Output is correct
3	Correct	173 ms	783436 KB	Output is correct
4	Correct	189 ms	783436 KB	Output is correct
5	Correct	169 ms	783436 KB	Output is correct
6	Correct	196 ms	783436 KB	Output is correct
7	Correct	193 ms	783436 KB	Output is correct
8	Correct	233 ms	783436 KB	Output is correct
9	Correct	163 ms	783436 KB	Output is correct
10	Correct	159 ms	783436 KB	Output is correct
11	Correct	186 ms	783436 KB	Output is correct
12	Correct	189 ms	783436 KB	Output is correct
13	Correct	213 ms	783436 KB	Output is correct
14	Correct	166 ms	783436 KB	Output is correct
15	Correct	196 ms	783436 KB	Output is correct
16	Correct	189 ms	783436 KB	Output is correct
17	Correct	216 ms	783436 KB	Output is correct
18	Correct	219 ms	783436 KB	Output is correct
19	Correct	179 ms	783436 KB	Output is correct
20	Correct	223 ms	783436 KB	Output is correct
21	Correct	176 ms	783436 KB	Output is correct
22	Correct	229 ms	783436 KB	Output is correct
23	Correct	206 ms	783436 KB	Output is correct
24	Correct	196 ms	783436 KB	Output is correct
25	Correct	203 ms	783700 KB	Output is correct
26	Correct	206 ms	783700 KB	Output is correct
27	Correct	213 ms	783700 KB	Output is correct
28	Correct	179 ms	783700 KB	Output is correct
29	Correct	163 ms	783700 KB	Output is correct
30	Correct	186 ms	783700 KB	Output is correct
31	Correct	213 ms	783700 KB	Output is correct
32	Correct	229 ms	783700 KB	Output is correct
33	Correct	216 ms	783700 KB	Output is correct
34	Correct	206 ms	783700 KB	Output is correct
35	Correct	199 ms	783436 KB	Output is correct
36	Correct	173 ms	783436 KB	Output is correct
37	Correct	189 ms	783964 KB	Output is correct
38	Correct	226 ms	783964 KB	Output is correct
39	Correct	199 ms	783568 KB	Output is correct
40	Correct	236 ms	783436 KB	Output is correct
41	Correct	173 ms	783568 KB	Output is correct
42	Correct	159 ms	783568 KB	Output is correct
43	Correct	169 ms	783700 KB	Output is correct
44	Correct	206 ms	783700 KB	Output is correct
45	Correct	633 ms	796944 KB	Output is correct
46	Correct	646 ms	798648 KB	Output is correct
47	Correct	566 ms	795764 KB	Output is correct
48	Correct	583 ms	798640 KB	Output is correct
49	Correct	589 ms	796412 KB	Output is correct
50	Correct	553 ms	797976 KB	Output is correct
51	Correct	563 ms	799052 KB	Output is correct
52	Correct	363 ms	784244 KB	Output is correct
53	Correct	326 ms	784244 KB	Output is correct
54	Correct	589 ms	816156 KB	Output is correct
55	Correct	603 ms	816156 KB	Output is correct
56	Correct	586 ms	815412 KB	Output is correct
57	Correct	403 ms	790980 KB	Output is correct
58	Correct	339 ms	784244 KB	Output is correct
59	Correct	416 ms	785040 KB	Output is correct
60	Correct	463 ms	789000 KB	Output is correct
61	Correct	546 ms	792168 KB	Output is correct
62	Correct	453 ms	790164 KB	Output is correct
63	Correct	453 ms	790864 KB	Output is correct
64	Correct	509 ms	793140 KB	Output is correct
65	Correct	2216 ms	886372 KB	Output is correct
66	Correct	2146 ms	886516 KB	Output is correct
67	Correct	506 ms	799624 KB	Output is correct
68	Correct	466 ms	799672 KB	Output is correct
69	Correct	513 ms	800864 KB	Output is correct
70	Correct	519 ms	800936 KB	Output is correct
71	Correct	403 ms	793316 KB	Output is correct
72	Correct	443 ms	793316 KB	Output is correct
73	Correct	403 ms	791848 KB	Output is correct
74	Correct	366 ms	791848 KB	Output is correct
75	Correct	479 ms	797692 KB	Output is correct
76	Correct	436 ms	797700 KB	Output is correct
77	Correct	446 ms	797700 KB	Output is correct
78	Correct	606 ms	798452 KB	Output is correct
79	Correct	599 ms	797196 KB	Output is correct
80	Runtime error	1606 ms	824792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Halted	0 ms	0 KB	-

답안 #36944

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 56.0 / 56.0

Subtask #4 0 / 22.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
56.0 / 56.0

Subtask #4
0 / 22.0