oj.uz

답안 #504144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
504144 2022-01-09T23:55:22 Z mjhmjh1104 Alternating Current (BOI18_alternating) C++17
0 / 100
 100 ms 11080 KB 
#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
using namespace std;

int tree[262144], lazy[262144];

void propagate(int i, int b, int e) {
    if (!lazy[i]) return;
    if (b != e) {
        lazy[i * 2 + 1] = lazy[i];
        lazy[i * 2 + 2] = lazy[i];
    }
    tree[i] = lazy[i];
    lazy[i] = 0;
}

int query(int i, int b, int e, int l, int r) {
    propagate(i, b, e);
    if (r < b || e < l) return 0;
    if (l <= b && e <= r) return tree[i];
    int m = (b + e) / 2;
    return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}

int update(int i, int b, int e, int l, int r, int v) {
    propagate(i, b, e);
    if (r < b || e < l) return tree[i];
    if (l <= b && e <= r) {
        lazy[i] = v;
        propagate(i, b, e);
        return tree[i];
    }
    int m = (b + e) / 2;
    return tree[i] = min(update(i * 2 + 1, b, m, l, r, v), update(i * 2 + 2, m + 1, e, l, r, v));
}

int n, m, x[100006], y[100006];
vector<int> adj[100006];
set<pair<int, int>> s;
vector<pair<int, int>> v;
int cl[100006];

bool dfs(int x) {
    for (auto &i: adj[x]) {
        if (!cl[i]) {
            cl[i] = -cl[x];
            if (dfs(i)) return true;
        } else if (cl[i] == cl[x]) return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", x + i, y + i);
        x[i]--, y[i]--;
        if (x[i] > y[i]) s.insert({ i, 0 });
        v.push_back({ x[i], -i - 1 });
        v.push_back({ y[i], i });
    }
    sort(v.begin(), v.end());
    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k < (int)v.size() && v[k] < make_pair(i, 0)) {
            if (v[k].second < 0) s.insert({ -v[k].second - 1, 0 });
            else s.erase({ v[k].second, 0 });
            k++;
        }
        if ((int)s.size() < 2) return puts("impossible"), 0;
        if ((int)s.size() == 2) {
            int first = s.begin()->first;
            int second = next(s.begin())->first;
            adj[first].push_back(second);
            adj[second].push_back(first);
        }
    }
    for (int i = 0; i < m; i++) if (!cl[i] && !adj[i].empty()) {
        cl[i] = -1;
        if (dfs(i)) return puts("impossible"), 0;
    }
    for (int i = 0; i < m; i++) if (cl[i]) {
        if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], cl[i]);
        else update(0, 0, 131071, 0, y[i], cl[i]), update(0, 0, 131071, x[i], n - 1, cl[i]);
    }
    for (int i = 0; i < m; i++) if (!cl[i]) {
        int t = 0;
        if (x[i] <= y[i]) t = query(0, 0, 131071, x[i], y[i]);
        else t = min(query(0, 0, 131071, 0, y[i]), query(0, 0, 131071, x[i], n - 1));
        if (t >= 0) cl[i] = -1;
        else cl[i] = 1;
        if (x[i] <= y[i]) update(0, 0, 131071, x[i], y[i], cl[i]);
        else update(0, 0, 131071, 0, y[i], cl[i]), update(0, 0, 131071, x[i], n - 1, cl[i]);
    }
    s.clear();
    for (int i = 0; i < m; i++) if (x[i] > y[i]) s.insert({ cl[i], i });
    for (int i = 0; i < m; i++) {
        if (cl[i] == -1) printf("0");
        else printf("1");
    }
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d%d", x + i, y + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 1 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 1 ms 2636 KB Output is correct
18 Correct 1 ms 2636 KB Output is correct
19 Correct 1 ms 2636 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 1 ms 2636 KB Output is correct
22 Correct 1 ms 2636 KB Output is correct
23 Correct 1 ms 2636 KB Output is correct
24 Correct 1 ms 2636 KB Output is correct
25 Correct 1 ms 2636 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 1 ms 2636 KB Output is correct
28 Correct 2 ms 2628 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 1 ms 2636 KB Output is correct
31 Correct 1 ms 2636 KB Output is correct
32 Correct 1 ms 2636 KB Output is correct
33 Correct 1 ms 2636 KB Output is correct
34 Correct 1 ms 2636 KB Output is correct
35 Correct 1 ms 2636 KB Output is correct
36 Incorrect 1 ms 2700 KB no wires in direction 0 between segments 14 and 14
37 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 1 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 1 ms 2636 KB Output is correct
18 Correct 1 ms 2636 KB Output is correct
19 Correct 1 ms 2636 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 1 ms 2636 KB Output is correct
22 Correct 1 ms 2636 KB Output is correct
23 Correct 1 ms 2636 KB Output is correct
24 Correct 1 ms 2636 KB Output is correct
25 Correct 1 ms 2636 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 1 ms 2636 KB Output is correct
28 Correct 2 ms 2628 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 1 ms 2636 KB Output is correct
31 Correct 1 ms 2636 KB Output is correct
32 Correct 1 ms 2636 KB Output is correct
33 Correct 1 ms 2636 KB Output is correct
34 Correct 1 ms 2636 KB Output is correct
35 Correct 1 ms 2636 KB Output is correct
36 Incorrect 1 ms 2700 KB no wires in direction 0 between segments 14 and 14
37 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 1 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 1 ms 2636 KB Output is correct
18 Correct 1 ms 2636 KB Output is correct
19 Correct 1 ms 2636 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 1 ms 2636 KB Output is correct
22 Correct 1 ms 2636 KB Output is correct
23 Correct 1 ms 2636 KB Output is correct
24 Correct 1 ms 2636 KB Output is correct
25 Correct 1 ms 2636 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 1 ms 2636 KB Output is correct
28 Correct 2 ms 2628 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 1 ms 2636 KB Output is correct
31 Correct 1 ms 2636 KB Output is correct
32 Correct 1 ms 2636 KB Output is correct
33 Correct 1 ms 2636 KB Output is correct
34 Correct 1 ms 2636 KB Output is correct
35 Correct 1 ms 2636 KB Output is correct
36 Incorrect 1 ms 2700 KB no wires in direction 0 between segments 14 and 14
37 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 10124 KB Output is correct
2 Correct 3 ms 3656 KB Output is correct
3 Correct 18 ms 4544 KB Output is correct
4 Correct 68 ms 8580 KB Output is correct
5 Correct 100 ms 11080 KB Output is correct
6 Correct 45 ms 6344 KB Output is correct
7 Incorrect 82 ms 10900 KB no wires in direction 0 between segments 41832 and 41832
8 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 1 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 1 ms 2636 KB Output is correct
18 Correct 1 ms 2636 KB Output is correct
19 Correct 1 ms 2636 KB Output is correct
20 Correct 1 ms 2636 KB Output is correct
21 Correct 1 ms 2636 KB Output is correct
22 Correct 1 ms 2636 KB Output is correct
23 Correct 1 ms 2636 KB Output is correct
24 Correct 1 ms 2636 KB Output is correct
25 Correct 1 ms 2636 KB Output is correct
26 Correct 1 ms 2636 KB Output is correct
27 Correct 1 ms 2636 KB Output is correct
28 Correct 2 ms 2628 KB Output is correct
29 Correct 2 ms 2636 KB Output is correct
30 Correct 1 ms 2636 KB Output is correct
31 Correct 1 ms 2636 KB Output is correct
32 Correct 1 ms 2636 KB Output is correct
33 Correct 1 ms 2636 KB Output is correct
34 Correct 1 ms 2636 KB Output is correct
35 Correct 1 ms 2636 KB Output is correct
36 Incorrect 1 ms 2700 KB no wires in direction 0 between segments 14 and 14
37 Halted 0 ms 0 KB -