Submission #953481

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
953481	2024-03-26T03:11:22 Z	Pring	Port Facility (JOI17_port_facility)	C++17	22 / 100	27 ms	32760 KB

port_facility

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 2005, mod = 1000000007;
int n;
pii p[MXN];
vector<int> edge[MXN];
int clr[MXN];

bool OVERLAP(pii a, pii b) {
    if (a.sc < b.fs) return false;
    return a.sc < b.sc;
}

bool DFS(int id, int c) {
    clr[id] = c;
    for (auto &i : edge[id]) {
        if (clr[i] == 0) {
            if (!DFS(i, c * -1)) return false;
        } else if (clr[i] == c) return false;
    }
    return true;
}

int miku() {
    cin >> n;
    FOR(i, 0, n) cin >> p[i].fs >> p[i].sc;
    sort(p, p + n);
    FOR(i, 0, n) FOR(j, i + 1, n) {
        if (OVERLAP(p[i], p[j])) {
            edge[i].push_back(j);
            edge[j].push_back(i);
        }
    }
    int ans = 1;
    FOR(i, 0, n) {
        if (clr[i]) continue;
        ans *= 2;
        ans -= (ans >= mod ? mod : 0);
        if (!DFS(i, 1)) return 0;
    }
    return ans;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    cout << miku() << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	512 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	7 ms	860 KB	Output is correct
26	Correct	6 ms	1332 KB	Output is correct
27	Correct	5 ms	860 KB	Output is correct
28	Correct	7 ms	1372 KB	Output is correct
29	Correct	6 ms	1036 KB	Output is correct
30	Correct	6 ms	1372 KB	Output is correct
31	Correct	6 ms	1112 KB	Output is correct
32	Correct	6 ms	856 KB	Output is correct
33	Correct	5 ms	860 KB	Output is correct
34	Correct	6 ms	860 KB	Output is correct
35	Correct	3 ms	536 KB	Output is correct
36	Correct	4 ms	560 KB	Output is correct
37	Correct	27 ms	32760 KB	Output is correct
38	Correct	15 ms	16596 KB	Output is correct
39	Correct	3 ms	604 KB	Output is correct
40	Correct	3 ms	348 KB	Output is correct
41	Correct	17 ms	16812 KB	Output is correct
42	Correct	20 ms	16928 KB	Output is correct
43	Correct	3 ms	604 KB	Output is correct
44	Correct	3 ms	604 KB	Output is correct

Subtask #3
0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	512 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	7 ms	860 KB	Output is correct
26	Correct	6 ms	1332 KB	Output is correct
27	Correct	5 ms	860 KB	Output is correct
28	Correct	7 ms	1372 KB	Output is correct
29	Correct	6 ms	1036 KB	Output is correct
30	Correct	6 ms	1372 KB	Output is correct
31	Correct	6 ms	1112 KB	Output is correct
32	Correct	6 ms	856 KB	Output is correct
33	Correct	5 ms	860 KB	Output is correct
34	Correct	6 ms	860 KB	Output is correct
35	Correct	3 ms	536 KB	Output is correct
36	Correct	4 ms	560 KB	Output is correct
37	Correct	27 ms	32760 KB	Output is correct
38	Correct	15 ms	16596 KB	Output is correct
39	Correct	3 ms	604 KB	Output is correct
40	Correct	3 ms	348 KB	Output is correct
41	Correct	17 ms	16812 KB	Output is correct
42	Correct	20 ms	16928 KB	Output is correct
43	Correct	3 ms	604 KB	Output is correct
44	Correct	3 ms	604 KB	Output is correct
45	Runtime error	1 ms	860 KB	Execution killed with signal 11
46	Halted	0 ms	0 KB	-

Subtask #4
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	512 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	7 ms	860 KB	Output is correct
26	Correct	6 ms	1332 KB	Output is correct
27	Correct	5 ms	860 KB	Output is correct
28	Correct	7 ms	1372 KB	Output is correct
29	Correct	6 ms	1036 KB	Output is correct
30	Correct	6 ms	1372 KB	Output is correct
31	Correct	6 ms	1112 KB	Output is correct
32	Correct	6 ms	856 KB	Output is correct
33	Correct	5 ms	860 KB	Output is correct
34	Correct	6 ms	860 KB	Output is correct
35	Correct	3 ms	536 KB	Output is correct
36	Correct	4 ms	560 KB	Output is correct
37	Correct	27 ms	32760 KB	Output is correct
38	Correct	15 ms	16596 KB	Output is correct
39	Correct	3 ms	604 KB	Output is correct
40	Correct	3 ms	348 KB	Output is correct
41	Correct	17 ms	16812 KB	Output is correct
42	Correct	20 ms	16928 KB	Output is correct
43	Correct	3 ms	604 KB	Output is correct
44	Correct	3 ms	604 KB	Output is correct
45	Runtime error	1 ms	860 KB	Execution killed with signal 11
46	Halted	0 ms	0 KB	-

Submission #953481

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 56.0

Subtask #4 0 / 22.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 56.0

Subtask #4
0 / 22.0