oj.uz

답안 #612420

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612420 2022-07-29T14:36:17 Z fvogel499 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 137816 KB 
// this code is bugged

#include "werewolf.h"
#include <bits/stdc++.h>

#define sz(x) ((x).size())

#define pii pair<int, int>
#define f first
#define s second

using namespace std;

const int inf = 1e9;
const int p2 = 1<<18;
const int siz = 4e5+40;
const int LG = 20;

struct Segtree {
    Segtree() {
        t = new int [p2*2];
        cls();
    }
    ~Segtree() {
        delete [] t;
    }
    void cls() {
        for (int i = 0; i < p2*2; i++) t[i] = -inf;
    }
    void upd(int x, int v) {
        for (x += p2; x; x /= 2) {
            t[x] = max(t[x], v);
        }
    }
    int get(int b, int e) {
        int r = -inf;
        b += p2;
        e += p2;
        while (b <= e) {
            if (b%2 == 1) {
                r = max(r, t[b]);
                b++;
            }
            if (e%2 == 0) {
                r = max(r, t[e]);
                e--;
            }
            b /= 2;
            e /= 2;
        }
        return r;
    }
    int* t;
};

vector<int> order [2];
vector<int> graph [2][siz];
vector<int> ett [2];
int posOfInEtt [2][siz];
int dsu [siz];
int jmp [2][siz][LG];
int smallerP2 [siz];

int gp(int x) {
    if (dsu[x] == x) return x;
    return dsu[x] = gp(dsu[x]);
}

bool merge(int x, int y) {
    x = gp(x);
    y = gp(y);
    if (x == y) return false;
    dsu[y] = x;
    return true;
}

void dfs(int T, int x, int p = -1) {
    ett[T].push_back(x);
    for (int y : graph[T][x]) if (y != p) {
        dfs(T, y, x);
        ett[T].push_back(x);
    }
}

int min(int x, int y) {
    return x < y ? x : y;
}

int max(int x, int y) {
    return x > y ? x : y;
}

int getMinZero(int start, int end) {
    int power = smallerP2[end-start+1];
    return min(jmp[0][start][power], jmp[0][end-(1<<power)+1][power]);
}

int getMaxOne(int start, int end) {
    int power = smallerP2[end-start+1];
    return max(jmp[1][start][power], jmp[1][end-(1<<power)+1][power]);
}

std::vector<int> check_validity(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB) {
    for (int i = 0; i < siz; i++) {
        smallerP2[i] = 0;
        while ((1<<(smallerP2[i]+1)) <= i) {
            smallerP2[i]++;
        }
    }
    vector<int> adj [n];
    for (int i = 0; i < sz(edgeX); i++) {
        adj[edgeX[i]].push_back(edgeY[i]);
        adj[edgeY[i]].push_back(edgeX[i]);
    }
    typedef int (*CompFunct) (int a, int b);
    CompFunct funct [2] = {min, max};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) order[i].push_back(j);
        if (i == 1) reverse(order[i].begin(), order[i].end());
        for (int j = 0; j < n; j++) dsu[j] = j;
        bool seen [n];
        for (int j = 0; j < n; j++) seen[j] = false;
        for (int jIdx = n-1; jIdx >= 0; jIdx--) {
            int j = order[i][jIdx];
            for (int k : adj[j]) if (seen[k]) {
                int pJ = gp(j);
                int pK = gp(k);
                if (pJ != pK) {
                    graph[i][pJ].push_back(pK);
                    graph[i][pK].push_back(pJ);
                    assert(merge(pJ, pK));
                }
            }
            seen[j] = true;
        }
        dfs(i, order[i][0]);
        assert(sz(ett[i]) == 2*n-1);
        for (int j = 0; j < 2*n-1; j++) {
            posOfInEtt[i][ett[i][j]] = j;
        }
        for (int j = 0; j < 2*n-1; j++) jmp[i][j][0] = ett[i][j];
        for (int j = 1; j < LG; j++) {
            for (int k = 0; k < 2*n-1; k++) {
                if (k+(1<<(j-1)) >= 2*n-1) {
                    jmp[i][k][j] = jmp[i][k][j-1];
                }
                else {
                    jmp[i][k][j] = funct[i](jmp[i][k][j-1], jmp[i][k+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    const int nbQ = sz(queryX);
    pii range [nbQ][2];
    for (int i = 0; i < nbQ; i++) {
        range[i][0] = {posOfInEtt[0][queryX[i]], posOfInEtt[0][queryX[i]]};
        for (int j = p2; j; j /= 2) {
            int prop = range[i][0].f-j;
            if (prop < 0) continue;
            if (getMinZero(prop, range[i][0].s) >= queryLB[i]) {
                range[i][0].f = prop;
            }
        }
        for (int j = p2; j; j /= 2) {
            int prop = range[i][0].s+j;
            if (prop >= 2*n-1) continue;
            if (getMinZero(range[i][0].f, prop) >= queryLB[i]) {
                range[i][0].s = prop;
            }
        }
    }
    for (int i = 0; i < nbQ; i++) {
        range[i][1] = {posOfInEtt[1][queryY[i]], posOfInEtt[1][queryY[i]]};
        for (int j = p2; j; j /= 2) {
            int prop = range[i][1].f-j;
            if (prop < 0) continue;
            if (getMaxOne(prop, range[i][1].s) <= queryRB[i]) {
                range[i][1].f = prop;
            }
        }
        for (int j = p2; j; j /= 2) {
            int prop = range[i][1].s+j;
            if (prop >= 2*n-1) continue;
            if (getMaxOne(range[i][1].f, prop) <= queryRB[i]) {
                range[i][1].s = prop;
            }
        }
    }
    vector<int> res(nbQ, 0);
    for (int i = 0; i < nbQ; i++) {
        set<int> se;
        for (int j = range[i][0].f; j <= range[i][0].s; j++) {
            se.insert(ett[0][j]);
        }
        for (int j = range[i][1].f; j <= range[i][1].s; j++) {
            if (se.count(ett[1][j])) {
                res[i] = 1;
                break;
            }
        }
    }
    return res;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i = 0; i < sz(edgeX); i++) {
      |                       ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from werewolf.cpp:4:
werewolf.cpp:137:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |         assert(sz(ett[i]) == 2*n-1);
      |                           ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 20692 KB Output is correct
2 Correct 16 ms 20712 KB Output is correct
3 Correct 15 ms 20692 KB Output is correct
4 Correct 16 ms 20624 KB Output is correct
5 Correct 22 ms 20708 KB Output is correct
6 Correct 21 ms 20692 KB Output is correct
7 Correct 17 ms 20692 KB Output is correct
8 Correct 22 ms 20692 KB Output is correct
9 Correct 17 ms 20724 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 20692 KB Output is correct
2 Correct 16 ms 20712 KB Output is correct
3 Correct 15 ms 20692 KB Output is correct
4 Correct 16 ms 20624 KB Output is correct
5 Correct 22 ms 20708 KB Output is correct
6 Correct 21 ms 20692 KB Output is correct
7 Correct 17 ms 20692 KB Output is correct
8 Correct 22 ms 20692 KB Output is correct
9 Correct 17 ms 20724 KB Output is correct
10 Correct 655 ms 22560 KB Output is correct
11 Correct 450 ms 22544 KB Output is correct
12 Correct 46 ms 22528 KB Output is correct
13 Correct 330 ms 22732 KB Output is correct
14 Correct 40 ms 22688 KB Output is correct
15 Correct 651 ms 22668 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 20692 KB Output is correct
2 Correct 16 ms 20712 KB Output is correct
3 Correct 15 ms 20692 KB Output is correct
4 Correct 16 ms 20624 KB Output is correct
5 Correct 22 ms 20708 KB Output is correct
6 Correct 21 ms 20692 KB Output is correct
7 Correct 17 ms 20692 KB Output is correct
8 Correct 22 ms 20692 KB Output is correct
9 Correct 17 ms 20724 KB Output is correct
10 Correct 655 ms 22560 KB Output is correct
11 Correct 450 ms 22544 KB Output is correct
12 Correct 46 ms 22528 KB Output is correct
13 Correct 330 ms 22732 KB Output is correct
14 Correct 40 ms 22688 KB Output is correct
15 Correct 651 ms 22668 KB Output is correct
16 Execution timed out 4010 ms 137816 KB Time limit exceeded
17 Halted 0 ms 0 KB -