제출 #566467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566467		elazarkoren	Werewolf (IOI18_werewolf)	C++17	15 / 100	4022 ms	31980 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 par[MAX_N], sz[MAX_N];

void init(int n) {
    iota(par, par + n, 0);
    fill(sz, sz + n, 1);
}

int Find(int i) {
    return par[i] == i ? i : par[i] = Find(par[i]);
}

bool Union(int a, int b) {
    int pa = Find(a), pb = Find(b);
    if (pa == pb) return false;
    if (sz[pa] < sz[pb]) swap(pa, pb);
    sz[pa] += sz[pb];
    par[pb] = pa;
    return true;
}

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();
//    iota(ind, ind + m, 0);
//    sort(ind, ind + m, [&] (int i, int j) {
//        return max(x[i], y[i]) < max(x[j], y[j]);
//    });
//    init(n);
    vvi graph(n);
//    for (int i = 0; i < m; i++) {
//        if (Union(x[ind[i]], y[ind[i]])) {
//            graph[x[ind[i]]].push_back(y[ind[i]]);
//            graph[y[ind[i]]].push_back(x[ind[i]]);
//        }
//    }
    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: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51