oj.uz

Submission #566403

# Submission time Handle Problem Language Result Execution time Memory
566403 2022-05-22T09:48:36 Z elazarkoren Werewolf (IOI18_werewolf) C++17
34 / 100
 1095 ms 34884 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

struct Seg {
    int n;
    vii seg;
    Seg (int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n, {0, n});
    }
    void update(int i, int x) {
        for (i += n; i; i >>= 1) {
            chkmax(seg[i].x, x);
            chkmin(seg[i].y, x);
        }
    }
    pii query(int l, int r) {
        pii ans = {0, n};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                chkmax(ans.x, seg[l].x);
                chkmin(ans.y, seg[l].y);
                l++;
            }
            if (r & 1) {
                --r;
                chkmax(ans.x, seg[r].x);
                chkmin(ans.y, seg[r].y);
            }
        }
        return ans;
    }
};

void DfsMax(vvi &graph, int node, int max, vb &visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (neighbor <= max && !visited[neighbor]) DfsMax(graph, neighbor, max, visited);
    }
}

void DfsMin(vvi &graph, int node, int min, vb &visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (neighbor >= min && !visited[neighbor]) DfsMin(graph, neighbor, min, visited);
    }
}

const int MAX_N = 2e5 + 5;

int ind[MAX_N];

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int m = x.size();
    vvi graph(n);
    for (int i = 0; i < m; i++) {
        graph[x[i]].push_back(y[i]);
        graph[y[i]].push_back(x[i]);
    }
    int start = 0;
    for (; start < n; start++) {
        if (graph[start].size() == 1) break;
    }
    bitset<MAX_N> visited;
    for (int i = 0; i < n; i++) {
        ind[start] = i;
        visited[start] = true;
        for (int neighbor : graph[start]) {
            if (!visited[neighbor]) {
                start = neighbor;
                break;
            }
        }
    }
    Seg seg(n);
    for (int i = 0; i < n; i++) {
        seg.update(ind[i], i);
    }
    int q = s.size();
    vi ans(q);
    for (int i = 0; i < q; i++) {
        int v = ind[s[i]], u = ind[e[i]];
        if (v < u) {
            int begin = v, end = u + 1, mid;
            while (begin < end) {
                mid = (begin + end) >> 1;
                if (seg.query(v, mid + 1).y < l[i]) end = mid;
                else begin = mid + 1;
            }
            int right = end - 1;
            begin = v, end = u;
            while (begin < end) {
                mid = (begin + end) >> 1;
                if (seg.query(mid, u).x > r[i]) begin = mid + 1;
                else end = mid;
            }
            int left = end;
            ans[i] = right >= left;
        } else {
            swap(v, u);
            int begin = v, end = u + 1, mid;
            while (begin < end) {
                mid = (begin + end) >> 1;
                if (seg.query(v, mid + 1).x > r[i]) end = mid;
                else begin = mid + 1;
            }
            int right = end - 1;
            begin = v, end = u;
            while (begin < end) {
                mid = (begin + end) >> 1;
                if (seg.query(mid, u).y < l[i]) begin = mid + 1;
                else end = mid;
            }
            int left = end;
            ans[i] = right >= left;
        }
//        vb visited1(n), visited2(n);
//        DfsMin(graph, s[i], l[i], visited1);
//        DfsMax(graph, e[i], r[i], visited2);
//        for (int j = 0; j < n; j++) {
//            if (visited1[j] && visited2[j]) {
//                ans[i] = 1;
//                break;
//            }
//        }
    }
    return ans;
}
//6 6 3
//0 3
//1 2
//1 5
//1 3
//2 5
//3 4
//
//4 2 1 2
//4 2 2 2
//5 4 3 4

//6 5 3
//1 3
//3 0
//0 4
//4 5
//5 2
//
//3 5 0 5
//2 1 0 4
//4 2 3 4

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 26372 KB Output is correct
2 Correct 964 ms 34804 KB Output is correct
3 Correct 965 ms 34808 KB Output is correct
4 Correct 910 ms 34808 KB Output is correct
5 Correct 880 ms 34800 KB Output is correct
6 Correct 804 ms 34788 KB Output is correct
7 Correct 903 ms 34828 KB Output is correct
8 Correct 958 ms 34800 KB Output is correct
9 Correct 453 ms 34884 KB Output is correct
10 Correct 497 ms 34764 KB Output is correct
11 Correct 616 ms 34708 KB Output is correct
12 Correct 492 ms 34824 KB Output is correct
13 Correct 984 ms 34800 KB Output is correct
14 Correct 1027 ms 34796 KB Output is correct
15 Correct 1054 ms 34796 KB Output is correct
16 Correct 1037 ms 34804 KB Output is correct
17 Correct 1095 ms 34800 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -