Submission #27812

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
27812	2017-07-14T06:54:41 Z	khsoo01	Port Facility (JOI17_port_facility)	C++11	100 / 100	2379 ms	114752 KB

port_facility

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int N = 1000005, mod = 1e9+7;
int n;
bool vis[N];

vector<int> st;
set<pii> s;

struct gugan {
	int s, e;
	bool operator < (const gugan &T) const {
		return e > T.e;
	}
} g[N];
vector<gugan> res[2];

int mgi (int A, int B) {
	if(A == -1) return B;
	if(B == -1) return A;
	return g[A].s < g[B].s ? A : B;
}

struct disj {
	int fr[N], op[N];
	void init () {
		for(int i=1;i<=n;i++) {
			fr[i] = i; op[i] = -1;
		}
	}
	int ff (int P) {
		if(fr[P] == P) return P;
		return fr[P] = ff(fr[P]);
	}
	int fo (int P) {
		if(op[P] == -1) return -1;
		return op[P] = ff(op[P]);
	}
	void Union (int A, int B) {
		A = ff(A); B = ff(B);
		if(op[A] == -1) op[A] = B;
		if(op[B] == -1) op[B] = A;
		op[A] = fo(A); op[B] = fo(B);
		int P = mgi(A, op[B]), Q = mgi(B, op[A]);
		fr[A] = P; fr[op[B]] = P;
		fr[B] = Q; fr[op[A]] = Q;
		op[P] = Q; op[Q] = P;
	}
} uf;

vector<pii> ev;

bool can (vector<gugan> &V) {
	ev.clear(); st.clear();
	for(int i=0;i<V.size();i++) {
		ev.push_back(pii(V[i].s, i+1));
		ev.push_back(pii(V[i].e, -i-1));
	}
	sort(ev.begin(), ev.end());
	for(int i=0;i<ev.size();i++) {
		int T = ev[i].Y;
		if(T < 0) {
			if(st.back() != -T) return false;
			st.pop_back();
		}
		else st.push_back(T);
	}
	return true;
}

int main()
{
	scanf("%d",&n); uf.init();
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&g[i].s,&g[i].e);
	}
	sort(g+1, g+1+n);
	for(int i=1;i<=n;i++) {
		while(!st.empty() && g[i].e < g[st.back()].s) {
			st.pop_back();
		}
		auto it = s.lower_bound(pii(g[i].s, 0));
		if(it != s.end() && (it->X) <= g[i].e) {
			int V = uf.ff(it->Y);
			while(!st.empty()) {
				int T = st.back(); st.pop_back();
				if(uf.ff(T) == V || uf.fo(T) == V) break;
				uf.Union(T, i);
			}
			uf.Union(V, i);
		}
		int A = uf.ff(i), B = uf.fo(i);
		st.push_back(mgi(A, B));
		s.insert(pii(g[i].s, i));
	}
	int ans = 1;
	for(int i=1;i<=n;i++) {
		if(uf.ff(i) == i && !vis[i]) {
			ans = (ans * 2) % mod;
			if(~uf.op[i]) vis[uf.fo(i)] = true;
		}
	}
	for(int i=1;i<=n;i++) {
		res[vis[uf.ff(i)]].push_back(g[i]);
	}
	if(!can(res[0]) || !can(res[1])) puts("0");
	else printf("%d\n",ans);
}

Compilation message

port_facility.cpp: In function 'bool can(std::vector<gugan>&)':
port_facility.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V.size();i++) {
               ^
port_facility.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ev.size();i++) {
               ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:76:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); uf.init();
                ^
port_facility.cpp:78:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&g[i].s,&g[i].e);
                                ^

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	18632 KB	Output is correct
2	Correct	18632 KB	Output is correct
3	Correct	18632 KB	Output is correct
4	Correct	18632 KB	Output is correct
5	Correct	18632 KB	Output is correct
6	Correct	18632 KB	Output is correct
7	Correct	18632 KB	Output is correct
8	Correct	18632 KB	Output is correct
9	Correct	18632 KB	Output is correct
10	Correct	18632 KB	Output is correct
11	Correct	18632 KB	Output is correct
12	Correct	18632 KB	Output is correct
13	Correct	18632 KB	Output is correct
14	Correct	18632 KB	Output is correct
15	Correct	18632 KB	Output is correct
16	Correct	18632 KB	Output is correct
17	Correct	18632 KB	Output is correct
18	Correct	18632 KB	Output is correct
19	Correct	18632 KB	Output is correct
20	Correct	18632 KB	Output is correct
21	Correct	18632 KB	Output is correct
22	Correct	18632 KB	Output is correct
23	Correct	18632 KB	Output is correct
24	Correct	18632 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	18632 KB	Output is correct
2	Correct	18632 KB	Output is correct
3	Correct	18632 KB	Output is correct
4	Correct	18632 KB	Output is correct
5	Correct	18632 KB	Output is correct
6	Correct	18632 KB	Output is correct
7	Correct	18632 KB	Output is correct
8	Correct	18632 KB	Output is correct
9	Correct	18632 KB	Output is correct
10	Correct	18632 KB	Output is correct
11	Correct	18632 KB	Output is correct
12	Correct	18632 KB	Output is correct
13	Correct	18632 KB	Output is correct
14	Correct	18632 KB	Output is correct
15	Correct	18632 KB	Output is correct
16	Correct	18632 KB	Output is correct
17	Correct	18632 KB	Output is correct
18	Correct	18632 KB	Output is correct
19	Correct	18632 KB	Output is correct
20	Correct	18632 KB	Output is correct
21	Correct	18632 KB	Output is correct
22	Correct	18632 KB	Output is correct
23	Correct	18632 KB	Output is correct
24	Correct	18632 KB	Output is correct
25	Correct	18896 KB	Output is correct
26	Correct	18764 KB	Output is correct
27	Correct	18896 KB	Output is correct
28	Correct	18764 KB	Output is correct
29	Correct	18764 KB	Output is correct
30	Correct	18896 KB	Output is correct
31	Correct	18764 KB	Output is correct
32	Correct	18896 KB	Output is correct
33	Correct	18764 KB	Output is correct
34	Correct	18896 KB	Output is correct
35	Correct	18764 KB	Output is correct
36	Correct	18768 KB	Output is correct
37	Correct	18764 KB	Output is correct
38	Correct	18764 KB	Output is correct
39	Correct	18764 KB	Output is correct
40	Correct	18764 KB	Output is correct
41	Correct	18764 KB	Output is correct
42	Correct	18764 KB	Output is correct
43	Correct	18764 KB	Output is correct
44	Correct	18764 KB	Output is correct

Subtask #3
56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	18632 KB	Output is correct
2	Correct	0 ms	18632 KB	Output is correct
3	Correct	0 ms	18632 KB	Output is correct
4	Correct	0 ms	18632 KB	Output is correct
5	Correct	0 ms	18632 KB	Output is correct
6	Correct	0 ms	18632 KB	Output is correct
7	Correct	0 ms	18632 KB	Output is correct
8	Correct	0 ms	18632 KB	Output is correct
9	Correct	0 ms	18632 KB	Output is correct
10	Correct	0 ms	18632 KB	Output is correct
11	Correct	0 ms	18632 KB	Output is correct
12	Correct	0 ms	18632 KB	Output is correct
13	Correct	0 ms	18632 KB	Output is correct
14	Correct	0 ms	18632 KB	Output is correct
15	Correct	0 ms	18632 KB	Output is correct
16	Correct	0 ms	18632 KB	Output is correct
17	Correct	0 ms	18632 KB	Output is correct
18	Correct	0 ms	18632 KB	Output is correct
19	Correct	0 ms	18632 KB	Output is correct
20	Correct	0 ms	18632 KB	Output is correct
21	Correct	0 ms	18632 KB	Output is correct
22	Correct	0 ms	18632 KB	Output is correct
23	Correct	0 ms	18632 KB	Output is correct
24	Correct	0 ms	18632 KB	Output is correct
25	Correct	0 ms	18896 KB	Output is correct
26	Correct	0 ms	18764 KB	Output is correct
27	Correct	0 ms	18896 KB	Output is correct
28	Correct	0 ms	18764 KB	Output is correct
29	Correct	0 ms	18764 KB	Output is correct
30	Correct	0 ms	18896 KB	Output is correct
31	Correct	0 ms	18764 KB	Output is correct
32	Correct	0 ms	18896 KB	Output is correct
33	Correct	0 ms	18764 KB	Output is correct
34	Correct	0 ms	18896 KB	Output is correct
35	Correct	0 ms	18764 KB	Output is correct
36	Correct	0 ms	18768 KB	Output is correct
37	Correct	0 ms	18764 KB	Output is correct
38	Correct	0 ms	18764 KB	Output is correct
39	Correct	0 ms	18764 KB	Output is correct
40	Correct	0 ms	18764 KB	Output is correct
41	Correct	0 ms	18764 KB	Output is correct
42	Correct	0 ms	18764 KB	Output is correct
43	Correct	0 ms	18764 KB	Output is correct
44	Correct	0 ms	18764 KB	Output is correct
45	Correct	86 ms	25972 KB	Output is correct
46	Correct	79 ms	25972 KB	Output is correct
47	Correct	89 ms	25976 KB	Output is correct
48	Correct	103 ms	25972 KB	Output is correct
49	Correct	96 ms	25972 KB	Output is correct
50	Correct	76 ms	25972 KB	Output is correct
51	Correct	76 ms	25972 KB	Output is correct
52	Correct	106 ms	27504 KB	Output is correct
53	Correct	106 ms	28020 KB	Output is correct
54	Correct	96 ms	26312 KB	Output is correct
55	Correct	76 ms	26084 KB	Output is correct
56	Correct	86 ms	26084 KB	Output is correct
57	Correct	96 ms	25972 KB	Output is correct
58	Correct	79 ms	27504 KB	Output is correct
59	Correct	76 ms	28788 KB	Output is correct
60	Correct	89 ms	28916 KB	Output is correct
61	Correct	96 ms	26004 KB	Output is correct
62	Correct	79 ms	28672 KB	Output is correct
63	Correct	79 ms	26036 KB	Output is correct
64	Correct	76 ms	26004 KB	Output is correct
65	Correct	129 ms	25972 KB	Output is correct
66	Correct	113 ms	25972 KB	Output is correct
67	Correct	79 ms	26232 KB	Output is correct
68	Correct	86 ms	26232 KB	Output is correct
69	Correct	96 ms	29556 KB	Output is correct
70	Correct	89 ms	29556 KB	Output is correct
71	Correct	93 ms	26232 KB	Output is correct
72	Correct	99 ms	26232 KB	Output is correct
73	Correct	96 ms	29556 KB	Output is correct
74	Correct	83 ms	29556 KB	Output is correct
75	Correct	93 ms	26312 KB	Output is correct
76	Correct	89 ms	26316 KB	Output is correct
77	Correct	83 ms	26316 KB	Output is correct
78	Correct	83 ms	25972 KB	Output is correct
79	Correct	79 ms	25972 KB	Output is correct

Subtask #4
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	18632 KB	Output is correct
2	Correct	0 ms	18632 KB	Output is correct
3	Correct	0 ms	18632 KB	Output is correct
4	Correct	0 ms	18632 KB	Output is correct
5	Correct	0 ms	18632 KB	Output is correct
6	Correct	0 ms	18632 KB	Output is correct
7	Correct	0 ms	18632 KB	Output is correct
8	Correct	0 ms	18632 KB	Output is correct
9	Correct	0 ms	18632 KB	Output is correct
10	Correct	0 ms	18632 KB	Output is correct
11	Correct	0 ms	18632 KB	Output is correct
12	Correct	0 ms	18632 KB	Output is correct
13	Correct	0 ms	18632 KB	Output is correct
14	Correct	0 ms	18632 KB	Output is correct
15	Correct	0 ms	18632 KB	Output is correct
16	Correct	0 ms	18632 KB	Output is correct
17	Correct	0 ms	18632 KB	Output is correct
18	Correct	0 ms	18632 KB	Output is correct
19	Correct	0 ms	18632 KB	Output is correct
20	Correct	0 ms	18632 KB	Output is correct
21	Correct	0 ms	18632 KB	Output is correct
22	Correct	0 ms	18632 KB	Output is correct
23	Correct	0 ms	18632 KB	Output is correct
24	Correct	0 ms	18632 KB	Output is correct
25	Correct	0 ms	18896 KB	Output is correct
26	Correct	0 ms	18764 KB	Output is correct
27	Correct	0 ms	18896 KB	Output is correct
28	Correct	0 ms	18764 KB	Output is correct
29	Correct	0 ms	18764 KB	Output is correct
30	Correct	0 ms	18896 KB	Output is correct
31	Correct	0 ms	18764 KB	Output is correct
32	Correct	0 ms	18896 KB	Output is correct
33	Correct	0 ms	18764 KB	Output is correct
34	Correct	0 ms	18896 KB	Output is correct
35	Correct	0 ms	18764 KB	Output is correct
36	Correct	0 ms	18768 KB	Output is correct
37	Correct	0 ms	18764 KB	Output is correct
38	Correct	0 ms	18764 KB	Output is correct
39	Correct	0 ms	18764 KB	Output is correct
40	Correct	0 ms	18764 KB	Output is correct
41	Correct	0 ms	18764 KB	Output is correct
42	Correct	0 ms	18764 KB	Output is correct
43	Correct	0 ms	18764 KB	Output is correct
44	Correct	0 ms	18764 KB	Output is correct
45	Correct	86 ms	25972 KB	Output is correct
46	Correct	79 ms	25972 KB	Output is correct
47	Correct	89 ms	25976 KB	Output is correct
48	Correct	103 ms	25972 KB	Output is correct
49	Correct	96 ms	25972 KB	Output is correct
50	Correct	76 ms	25972 KB	Output is correct
51	Correct	76 ms	25972 KB	Output is correct
52	Correct	106 ms	27504 KB	Output is correct
53	Correct	106 ms	28020 KB	Output is correct
54	Correct	96 ms	26312 KB	Output is correct
55	Correct	76 ms	26084 KB	Output is correct
56	Correct	86 ms	26084 KB	Output is correct
57	Correct	96 ms	25972 KB	Output is correct
58	Correct	79 ms	27504 KB	Output is correct
59	Correct	76 ms	28788 KB	Output is correct
60	Correct	89 ms	28916 KB	Output is correct
61	Correct	96 ms	26004 KB	Output is correct
62	Correct	79 ms	28672 KB	Output is correct
63	Correct	79 ms	26036 KB	Output is correct
64	Correct	76 ms	26004 KB	Output is correct
65	Correct	129 ms	25972 KB	Output is correct
66	Correct	113 ms	25972 KB	Output is correct
67	Correct	79 ms	26232 KB	Output is correct
68	Correct	86 ms	26232 KB	Output is correct
69	Correct	96 ms	29556 KB	Output is correct
70	Correct	89 ms	29556 KB	Output is correct
71	Correct	93 ms	26232 KB	Output is correct
72	Correct	99 ms	26232 KB	Output is correct
73	Correct	96 ms	29556 KB	Output is correct
74	Correct	83 ms	29556 KB	Output is correct
75	Correct	93 ms	26312 KB	Output is correct
76	Correct	89 ms	26316 KB	Output is correct
77	Correct	83 ms	26316 KB	Output is correct
78	Correct	83 ms	25972 KB	Output is correct
79	Correct	79 ms	25972 KB	Output is correct
80	Correct	1043 ms	102464 KB	Output is correct
81	Correct	953 ms	102480 KB	Output is correct
82	Correct	983 ms	102496 KB	Output is correct
83	Correct	959 ms	102472 KB	Output is correct
84	Correct	1029 ms	102464 KB	Output is correct
85	Correct	956 ms	102480 KB	Output is correct
86	Correct	1026 ms	102480 KB	Output is correct
87	Correct	1073 ms	98364 KB	Output is correct
88	Correct	1086 ms	102464 KB	Output is correct
89	Correct	1096 ms	90640 KB	Output is correct
90	Correct	1099 ms	88300 KB	Output is correct
91	Correct	1116 ms	88296 KB	Output is correct
92	Correct	1089 ms	86080 KB	Output is correct
93	Correct	1036 ms	98364 KB	Output is correct
94	Correct	1056 ms	110656 KB	Output is correct
95	Correct	1002 ms	111168 KB	Output is correct
96	Correct	963 ms	102596 KB	Output is correct
97	Correct	933 ms	111680 KB	Output is correct
98	Correct	986 ms	102980 KB	Output is correct
99	Correct	853 ms	102496 KB	Output is correct
100	Correct	2379 ms	86080 KB	Output is correct
101	Correct	2329 ms	86080 KB	Output is correct
102	Correct	1086 ms	88132 KB	Output is correct
103	Correct	1203 ms	88132 KB	Output is correct
104	Correct	1159 ms	114752 KB	Output is correct
105	Correct	1166 ms	114752 KB	Output is correct
106	Correct	1066 ms	88132 KB	Output is correct
107	Correct	1209 ms	88132 KB	Output is correct
108	Correct	1209 ms	114752 KB	Output is correct
109	Correct	1206 ms	114752 KB	Output is correct
110	Correct	1186 ms	90640 KB	Output is correct
111	Correct	1196 ms	90640 KB	Output is correct
112	Correct	1089 ms	90644 KB	Output is correct
113	Correct	933 ms	102496 KB	Output is correct
114	Correct	983 ms	102472 KB	Output is correct

Submission #27812

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 56.0 / 56.0

Subtask #4 22.0 / 22.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
56.0 / 56.0

Subtask #4
22.0 / 22.0