oj.uz

답안 #612422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612422 2022-07-29T14:38:32 Z fvogel499 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 136500 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 17 ms 20680 KB Output is correct
3 Correct 22 ms 20608 KB Output is correct
4 Correct 16 ms 20648 KB Output is correct
5 Correct 16 ms 20728 KB Output is correct
6 Correct 18 ms 20692 KB Output is correct
7 Correct 16 ms 20624 KB Output is correct
8 Correct 16 ms 20692 KB Output is correct
9 Correct 16 ms 20756 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 20692 KB Output is correct
2 Correct 17 ms 20680 KB Output is correct
3 Correct 22 ms 20608 KB Output is correct
4 Correct 16 ms 20648 KB Output is correct
5 Correct 16 ms 20728 KB Output is correct
6 Correct 18 ms 20692 KB Output is correct
7 Correct 16 ms 20624 KB Output is correct
8 Correct 16 ms 20692 KB Output is correct
9 Correct 16 ms 20756 KB Output is correct
10 Correct 671 ms 22456 KB Output is correct
11 Correct 463 ms 22356 KB Output is correct
12 Correct 48 ms 22416 KB Output is correct
13 Correct 348 ms 22548 KB Output is correct
14 Correct 41 ms 22632 KB Output is correct
15 Correct 644 ms 22496 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4100 ms 136500 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 17 ms 20680 KB Output is correct
3 Correct 22 ms 20608 KB Output is correct
4 Correct 16 ms 20648 KB Output is correct
5 Correct 16 ms 20728 KB Output is correct
6 Correct 18 ms 20692 KB Output is correct
7 Correct 16 ms 20624 KB Output is correct
8 Correct 16 ms 20692 KB Output is correct
9 Correct 16 ms 20756 KB Output is correct
10 Correct 671 ms 22456 KB Output is correct
11 Correct 463 ms 22356 KB Output is correct
12 Correct 48 ms 22416 KB Output is correct
13 Correct 348 ms 22548 KB Output is correct
14 Correct 41 ms 22632 KB Output is correct
15 Correct 644 ms 22496 KB Output is correct
16 Execution timed out 4100 ms 136500 KB Time limit exceeded
17 Halted 0 ms 0 KB -