oj.uz

Submission #505173

# Submission time Handle Problem Language Result Execution time Memory
505173 2022-01-10T22:20:18 Z mjhmjh1104 Alternating Current (BOI18_alternating) C++17
0 / 100
 103 ms 10104 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] = min(lazy[i * 2 + 1], lazy[i]);
        lazy[i * 2 + 2] = min(lazy[i * 2 + 2], lazy[i]);
    }
    tree[i] = min(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<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);
        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);
            else s.erase(v[k].second);
            k++;
        }
        if ((int)s.size() < 2) return puts("impossible"), 0;
        if ((int)s.size() == 2) {
            int first = *s.begin();
            int second = *next(s.begin());
            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]);
    }
    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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Incorrect 1 ms 2636 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Incorrect 1 ms 2636 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Incorrect 1 ms 2636 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10104 KB Output is correct
2 Correct 3 ms 3648 KB Output is correct
3 Correct 15 ms 4036 KB Output is correct
4 Correct 67 ms 7956 KB Output is correct
5 Correct 91 ms 9904 KB Output is correct
6 Correct 41 ms 5312 KB Output is correct
7 Incorrect 103 ms 9872 KB no wires in direction 0 between segments 41832 and 41832
8 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Incorrect 1 ms 2636 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -