oj.uz

답안 #566467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566467 2022-05-22T10:39:47 Z elazarkoren 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 31980 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 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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 263 ms 704 KB Output is correct
11 Correct 151 ms 668 KB Output is correct
12 Correct 18 ms 848 KB Output is correct
13 Correct 267 ms 712 KB Output is correct
14 Correct 174 ms 660 KB Output is correct
15 Correct 268 ms 860 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4022 ms 31980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 263 ms 704 KB Output is correct
11 Correct 151 ms 668 KB Output is correct
12 Correct 18 ms 848 KB Output is correct
13 Correct 267 ms 712 KB Output is correct
14 Correct 174 ms 660 KB Output is correct
15 Correct 268 ms 860 KB Output is correct
16 Execution timed out 4022 ms 31980 KB Time limit exceeded
17 Halted 0 ms 0 KB -