Submission #110183

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
110183	2019-05-09T21:21:56 Z	tincamatei	Port Facility (JOI17_port_facility)	C++14	100 / 100	3847 ms	144760 KB

port_facility

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int MOD = 1000000007;
int ev[1+2*MAX_N];
int first[1+MAX_N], last[1+MAX_N];

vector<int> graph[1+MAX_N];
int color[1+MAX_N];
bool bipartite = true;

void dfs(int nod, int c = 1) {
	color[nod] = c;
	for(auto it: graph[nod])
		if(color[it] == 0)
			dfs(it, 3 - c);
		else if(color[it] + color[nod] != 3)
			bipartite = false;
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, rez = 1;
	
	fscanf(fin, "%d", &n);

	for(int i = 1; i <= n; ++i) {
		fscanf(fin, "%d%d", &first[i], &last[i]);
		ev[first[i]] = i;
		ev[last[i]] = -i;
	}

	set<pair<int, int> > heads;
	for(int i = 1; i <= 2 * n; ++i) {
		if(ev[i] > 0)
			heads.insert(make_pair(i, ev[i]));
		else {
			ev[i] = -ev[i];

			set<pair<int, int> >::iterator it;
			it = heads.upper_bound(make_pair(first[ev[i]], ev[i]));

			int rightest = -1;
			while(it != heads.end()) {
				graph[it->second].push_back(ev[i]);
				graph[ev[i]].push_back(it->second);
				if(rightest == -1 || (rightest != -1 && last[it->second] > last[rightest]))
					rightest = it->second;
				it = heads.erase(it);
			}
			
			if(rightest != -1)
				heads.insert(make_pair(first[rightest], rightest));
			heads.erase(make_pair(first[ev[i]], ev[i]));
		}
	}

	for(int i = 1; i <= n; ++i)
		if(color[i] == 0) {
			dfs(i);
			rez = rez * 2 % MOD;
		}
	
	if(!bipartite)
		rez = 0;

	set<int> c[2];
	for(int i = 1; i <= 2 * n; ++i) {
		if(first[ev[i]] == i)
			c[color[ev[i]] - 1].insert(i);
		else {
			if(c[color[ev[i]] - 1].upper_bound(first[ev[i]]) != c[color[ev[i]] - 1].end())
				rez = 0;
			c[color[ev[i]] - 1].erase(first[ev[i]]);
		}
	}

	fprintf(fout, "%d", rez);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message

port_facility.cpp: In function 'int main()':
port_facility.cpp:34:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d", &n);
  ~~~~~~^~~~~~~~~~~~~~~
port_facility.cpp:37:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &first[i], &last[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23808 KB	Output is correct
2	Correct	23 ms	23800 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23900 KB	Output is correct
5	Correct	26 ms	23808 KB	Output is correct
6	Correct	25 ms	23808 KB	Output is correct
7	Correct	23 ms	23780 KB	Output is correct
8	Correct	23 ms	23800 KB	Output is correct
9	Correct	24 ms	23808 KB	Output is correct
10	Correct	24 ms	23808 KB	Output is correct
11	Correct	24 ms	23808 KB	Output is correct
12	Correct	23 ms	23808 KB	Output is correct
13	Correct	26 ms	23808 KB	Output is correct
14	Correct	24 ms	23808 KB	Output is correct
15	Correct	27 ms	23760 KB	Output is correct
16	Correct	26 ms	23808 KB	Output is correct
17	Correct	31 ms	23800 KB	Output is correct
18	Correct	26 ms	23808 KB	Output is correct
19	Correct	25 ms	23800 KB	Output is correct
20	Correct	24 ms	23808 KB	Output is correct
21	Correct	31 ms	23800 KB	Output is correct
22	Correct	28 ms	23808 KB	Output is correct
23	Correct	29 ms	23800 KB	Output is correct
24	Correct	26 ms	23808 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23808 KB	Output is correct
2	Correct	23 ms	23800 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23900 KB	Output is correct
5	Correct	26 ms	23808 KB	Output is correct
6	Correct	25 ms	23808 KB	Output is correct
7	Correct	23 ms	23780 KB	Output is correct
8	Correct	23 ms	23800 KB	Output is correct
9	Correct	24 ms	23808 KB	Output is correct
10	Correct	24 ms	23808 KB	Output is correct
11	Correct	24 ms	23808 KB	Output is correct
12	Correct	23 ms	23808 KB	Output is correct
13	Correct	26 ms	23808 KB	Output is correct
14	Correct	24 ms	23808 KB	Output is correct
15	Correct	27 ms	23760 KB	Output is correct
16	Correct	26 ms	23808 KB	Output is correct
17	Correct	31 ms	23800 KB	Output is correct
18	Correct	26 ms	23808 KB	Output is correct
19	Correct	25 ms	23800 KB	Output is correct
20	Correct	24 ms	23808 KB	Output is correct
21	Correct	31 ms	23800 KB	Output is correct
22	Correct	28 ms	23808 KB	Output is correct
23	Correct	29 ms	23800 KB	Output is correct
24	Correct	26 ms	23808 KB	Output is correct
25	Correct	30 ms	23928 KB	Output is correct
26	Correct	27 ms	23936 KB	Output is correct
27	Correct	26 ms	23936 KB	Output is correct
28	Correct	26 ms	23928 KB	Output is correct
29	Correct	26 ms	23928 KB	Output is correct
30	Correct	28 ms	24064 KB	Output is correct
31	Correct	28 ms	24064 KB	Output is correct
32	Correct	27 ms	24064 KB	Output is correct
33	Correct	30 ms	23940 KB	Output is correct
34	Correct	26 ms	23928 KB	Output is correct
35	Correct	29 ms	23936 KB	Output is correct
36	Correct	26 ms	24056 KB	Output is correct
37	Correct	28 ms	24056 KB	Output is correct
38	Correct	26 ms	23936 KB	Output is correct
39	Correct	29 ms	23928 KB	Output is correct
40	Correct	28 ms	23936 KB	Output is correct
41	Correct	26 ms	24064 KB	Output is correct
42	Correct	28 ms	24064 KB	Output is correct
43	Correct	28 ms	24056 KB	Output is correct
44	Correct	30 ms	24056 KB	Output is correct

Subtask #3
56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23808 KB	Output is correct
2	Correct	23 ms	23800 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23900 KB	Output is correct
5	Correct	26 ms	23808 KB	Output is correct
6	Correct	25 ms	23808 KB	Output is correct
7	Correct	23 ms	23780 KB	Output is correct
8	Correct	23 ms	23800 KB	Output is correct
9	Correct	24 ms	23808 KB	Output is correct
10	Correct	24 ms	23808 KB	Output is correct
11	Correct	24 ms	23808 KB	Output is correct
12	Correct	23 ms	23808 KB	Output is correct
13	Correct	26 ms	23808 KB	Output is correct
14	Correct	24 ms	23808 KB	Output is correct
15	Correct	27 ms	23760 KB	Output is correct
16	Correct	26 ms	23808 KB	Output is correct
17	Correct	31 ms	23800 KB	Output is correct
18	Correct	26 ms	23808 KB	Output is correct
19	Correct	25 ms	23800 KB	Output is correct
20	Correct	24 ms	23808 KB	Output is correct
21	Correct	31 ms	23800 KB	Output is correct
22	Correct	28 ms	23808 KB	Output is correct
23	Correct	29 ms	23800 KB	Output is correct
24	Correct	26 ms	23808 KB	Output is correct
25	Correct	30 ms	23928 KB	Output is correct
26	Correct	27 ms	23936 KB	Output is correct
27	Correct	26 ms	23936 KB	Output is correct
28	Correct	26 ms	23928 KB	Output is correct
29	Correct	26 ms	23928 KB	Output is correct
30	Correct	28 ms	24064 KB	Output is correct
31	Correct	28 ms	24064 KB	Output is correct
32	Correct	27 ms	24064 KB	Output is correct
33	Correct	30 ms	23940 KB	Output is correct
34	Correct	26 ms	23928 KB	Output is correct
35	Correct	29 ms	23936 KB	Output is correct
36	Correct	26 ms	24056 KB	Output is correct
37	Correct	28 ms	24056 KB	Output is correct
38	Correct	26 ms	23936 KB	Output is correct
39	Correct	29 ms	23928 KB	Output is correct
40	Correct	28 ms	23936 KB	Output is correct
41	Correct	26 ms	24064 KB	Output is correct
42	Correct	28 ms	24064 KB	Output is correct
43	Correct	28 ms	24056 KB	Output is correct
44	Correct	30 ms	24056 KB	Output is correct
45	Correct	237 ms	32404 KB	Output is correct
46	Correct	168 ms	32632 KB	Output is correct
47	Correct	186 ms	32196 KB	Output is correct
48	Correct	155 ms	32760 KB	Output is correct
49	Correct	173 ms	32220 KB	Output is correct
50	Correct	197 ms	32504 KB	Output is correct
51	Correct	167 ms	32760 KB	Output is correct
52	Correct	72 ms	27012 KB	Output is correct
53	Correct	133 ms	31804 KB	Output is correct
54	Correct	165 ms	35832 KB	Output is correct
55	Correct	207 ms	33672 KB	Output is correct
56	Correct	145 ms	33500 KB	Output is correct
57	Correct	82 ms	30172 KB	Output is correct
58	Correct	80 ms	27020 KB	Output is correct
59	Correct	143 ms	29180 KB	Output is correct
60	Correct	165 ms	30584 KB	Output is correct
61	Correct	193 ms	31096 KB	Output is correct
62	Correct	129 ms	30200 KB	Output is correct
63	Correct	142 ms	30852 KB	Output is correct
64	Correct	167 ms	31288 KB	Output is correct
65	Correct	264 ms	33416 KB	Output is correct
66	Correct	222 ms	33140 KB	Output is correct
67	Correct	171 ms	32868 KB	Output is correct
68	Correct	144 ms	32888 KB	Output is correct
69	Correct	199 ms	33736 KB	Output is correct
70	Correct	138 ms	33756 KB	Output is correct
71	Correct	144 ms	35448 KB	Output is correct
72	Correct	141 ms	35448 KB	Output is correct
73	Correct	137 ms	35704 KB	Output is correct
74	Correct	168 ms	35828 KB	Output is correct
75	Correct	151 ms	33272 KB	Output is correct
76	Correct	126 ms	34936 KB	Output is correct
77	Correct	132 ms	34936 KB	Output is correct
78	Correct	154 ms	32532 KB	Output is correct
79	Correct	139 ms	32296 KB	Output is correct

Subtask #4
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23808 KB	Output is correct
2	Correct	23 ms	23800 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23900 KB	Output is correct
5	Correct	26 ms	23808 KB	Output is correct
6	Correct	25 ms	23808 KB	Output is correct
7	Correct	23 ms	23780 KB	Output is correct
8	Correct	23 ms	23800 KB	Output is correct
9	Correct	24 ms	23808 KB	Output is correct
10	Correct	24 ms	23808 KB	Output is correct
11	Correct	24 ms	23808 KB	Output is correct
12	Correct	23 ms	23808 KB	Output is correct
13	Correct	26 ms	23808 KB	Output is correct
14	Correct	24 ms	23808 KB	Output is correct
15	Correct	27 ms	23760 KB	Output is correct
16	Correct	26 ms	23808 KB	Output is correct
17	Correct	31 ms	23800 KB	Output is correct
18	Correct	26 ms	23808 KB	Output is correct
19	Correct	25 ms	23800 KB	Output is correct
20	Correct	24 ms	23808 KB	Output is correct
21	Correct	31 ms	23800 KB	Output is correct
22	Correct	28 ms	23808 KB	Output is correct
23	Correct	29 ms	23800 KB	Output is correct
24	Correct	26 ms	23808 KB	Output is correct
25	Correct	30 ms	23928 KB	Output is correct
26	Correct	27 ms	23936 KB	Output is correct
27	Correct	26 ms	23936 KB	Output is correct
28	Correct	26 ms	23928 KB	Output is correct
29	Correct	26 ms	23928 KB	Output is correct
30	Correct	28 ms	24064 KB	Output is correct
31	Correct	28 ms	24064 KB	Output is correct
32	Correct	27 ms	24064 KB	Output is correct
33	Correct	30 ms	23940 KB	Output is correct
34	Correct	26 ms	23928 KB	Output is correct
35	Correct	29 ms	23936 KB	Output is correct
36	Correct	26 ms	24056 KB	Output is correct
37	Correct	28 ms	24056 KB	Output is correct
38	Correct	26 ms	23936 KB	Output is correct
39	Correct	29 ms	23928 KB	Output is correct
40	Correct	28 ms	23936 KB	Output is correct
41	Correct	26 ms	24064 KB	Output is correct
42	Correct	28 ms	24064 KB	Output is correct
43	Correct	28 ms	24056 KB	Output is correct
44	Correct	30 ms	24056 KB	Output is correct
45	Correct	237 ms	32404 KB	Output is correct
46	Correct	168 ms	32632 KB	Output is correct
47	Correct	186 ms	32196 KB	Output is correct
48	Correct	155 ms	32760 KB	Output is correct
49	Correct	173 ms	32220 KB	Output is correct
50	Correct	197 ms	32504 KB	Output is correct
51	Correct	167 ms	32760 KB	Output is correct
52	Correct	72 ms	27012 KB	Output is correct
53	Correct	133 ms	31804 KB	Output is correct
54	Correct	165 ms	35832 KB	Output is correct
55	Correct	207 ms	33672 KB	Output is correct
56	Correct	145 ms	33500 KB	Output is correct
57	Correct	82 ms	30172 KB	Output is correct
58	Correct	80 ms	27020 KB	Output is correct
59	Correct	143 ms	29180 KB	Output is correct
60	Correct	165 ms	30584 KB	Output is correct
61	Correct	193 ms	31096 KB	Output is correct
62	Correct	129 ms	30200 KB	Output is correct
63	Correct	142 ms	30852 KB	Output is correct
64	Correct	167 ms	31288 KB	Output is correct
65	Correct	264 ms	33416 KB	Output is correct
66	Correct	222 ms	33140 KB	Output is correct
67	Correct	171 ms	32868 KB	Output is correct
68	Correct	144 ms	32888 KB	Output is correct
69	Correct	199 ms	33736 KB	Output is correct
70	Correct	138 ms	33756 KB	Output is correct
71	Correct	144 ms	35448 KB	Output is correct
72	Correct	141 ms	35448 KB	Output is correct
73	Correct	137 ms	35704 KB	Output is correct
74	Correct	168 ms	35828 KB	Output is correct
75	Correct	151 ms	33272 KB	Output is correct
76	Correct	126 ms	34936 KB	Output is correct
77	Correct	132 ms	34936 KB	Output is correct
78	Correct	154 ms	32532 KB	Output is correct
79	Correct	139 ms	32296 KB	Output is correct
80	Correct	2088 ms	109936 KB	Output is correct
81	Correct	2160 ms	109772 KB	Output is correct
82	Correct	2220 ms	108920 KB	Output is correct
83	Correct	2066 ms	109700 KB	Output is correct
84	Correct	2039 ms	110140 KB	Output is correct
85	Correct	2057 ms	109396 KB	Output is correct
86	Correct	2050 ms	110192 KB	Output is correct
87	Correct	759 ms	58148 KB	Output is correct
88	Correct	1740 ms	105080 KB	Output is correct
89	Correct	2560 ms	144760 KB	Output is correct
90	Correct	2443 ms	121088 KB	Output is correct
91	Correct	2448 ms	120992 KB	Output is correct
92	Correct	1306 ms	89476 KB	Output is correct
93	Correct	754 ms	58232 KB	Output is correct
94	Correct	1546 ms	85496 KB	Output is correct
95	Correct	1887 ms	97608 KB	Output is correct
96	Correct	1994 ms	100728 KB	Output is correct
97	Correct	1662 ms	90016 KB	Output is correct
98	Correct	1819 ms	98368 KB	Output is correct
99	Correct	1893 ms	100984 KB	Output is correct
100	Correct	3511 ms	120816 KB	Output is correct
101	Correct	3847 ms	120308 KB	Output is correct
102	Correct	2131 ms	115820 KB	Output is correct
103	Correct	2267 ms	115820 KB	Output is correct
104	Correct	2077 ms	124004 KB	Output is correct
105	Correct	2028 ms	123876 KB	Output is correct
106	Correct	2417 ms	140504 KB	Output is correct
107	Correct	2580 ms	140328 KB	Output is correct
108	Correct	2392 ms	142556 KB	Output is correct
109	Correct	2572 ms	142528 KB	Output is correct
110	Correct	1456 ms	135312 KB	Output is correct
111	Correct	1526 ms	136392 KB	Output is correct
112	Correct	1478 ms	136368 KB	Output is correct
113	Correct	2039 ms	109016 KB	Output is correct
114	Correct	2077 ms	109560 KB	Output is correct

Submission #110183

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