Submission #566397

#	Time	Username	Problem	Language	Result	Execution time	Memory
566397		elazarkoren	Werewolf (IOI18_werewolf)	C++17	0 / 100	519 ms	26376 KiB

werewolf

#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++) {
        if (s[i] < l[i] || r[i] < e[i]) continue;
        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 {
            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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51