Submission #342440

#	Time	Username	Problem	Language	Result	Execution time	Memory
342440		cuongdh1912	늑대인간 (IOI18_werewolf)	C++14	0 / 100	4073 ms	29132 KiB

werewolf

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

#define FOR(i, n) for (int i = 0; i < n; ++i)
using namespace std;

int findIndex2Insert(vector<int> pathi, int yi) {
    if (pathi.size() == 0) {
        return 0;
    }
    int mid = 0;
    int left = 0, right = pathi.size() - 1;
    while (left < right) {
        mid = (left + right) / 2;
        if (yi <= pathi[mid]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    if (yi > pathi[left]) {
        ++left;
    }
    return left;
}
int findIndex(vector<int> pathi, int yi) {
    if (pathi.size() == 0) {
        return 0;
    }
    int mid = 0;
    int left = 0, right = pathi.size() - 1;
    while (left < right) {
        mid = (left + right) / 2;
        if (yi <= pathi[mid]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    if (yi > pathi[left] && left < pathi.size() - 1) {
        ++left;
    } else if (yi < pathi[left] && left > 0) {
        --left;
    }
    return left;
}
enum State {
    Wolf,
    Humance,
    Mid
};
enum SelectState {
    NoSelected,
    SelectedWolf,
    SelectedHumance,
    SelectedBoth
};
struct Vertex {
    int index;
    State state;
};

State getState(int si, int li, int ri) {
    if (si < li) {
        return Wolf;
    } else if (si > ri) {
        return Humance;
    } else {
        return Mid;
    }
}

Vertex initVertex(int index, State state) {
    Vertex vertex = Vertex();
    vertex.index = index;
    vertex.state = state;
    return vertex;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();
    int M = X.size();
    std::vector<int> A(Q);
    vector<vector<int>> path(N);
    FOR(i, M) {
        int xi = X[i];
        int yi = Y[i];
        // push Y[i] to path descendingly by using binary insert
        int index = findIndex2Insert(path[xi], yi);
        path[xi].insert(path[xi].begin() + index, yi);
        index = findIndex2Insert(path[yi], xi);
        path[yi].insert(path[yi].begin() + index, xi);
    }
    for (int i = 0; i < Q; ++i) {
        A[i] = 0;
        queue<Vertex> qVertex;
        int li = L[i], ri = R[i];
        vector<State> v(N);
        vector<SelectState> selectedV(N);
        fill(selectedV.begin(), selectedV.end(), NoSelected);
        
        Vertex vertex = initVertex(S[i], Humance);
        qVertex.push(vertex);
        
        selectedV[S[i]] = SelectedBoth;
        while (!qVertex.empty()) {
            Vertex vi = qVertex.front();
            qVertex.pop();
            if (vi.index == E[i] && vi.state == Wolf) {
                A[i] = 1;
                break;
            }
            vector<int> vertices = path[vi.index];
            if (vertices.size() == 0) { continue;}
            int iLi = findIndex(vertices, li);
            int iRi = findIndex(vertices, ri);
            if (vi.state == Humance) {
                for (int j = iRi; j < path[vi.index].size(); ++j) {
                    if ((selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedWolf) && vertices[j] > ri) {
                        Vertex vertex = initVertex(vertices[j], Humance);
                        qVertex.push(vertex);
                        selectedV[vertices[j]] = SelectedBoth;
                    }
                }
                for (int j = iLi; j <= iRi; ++j) {
                    if (vertices[j] >= li && vertices[j] <= ri) {
                        if (selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedWolf) {
                            Vertex vertex = initVertex(vertices[j], Humance);
                            qVertex.push(vertex);
                        }
                        if ((selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedHumance) && vertices[j] <= ri) {
                            Vertex vertex = initVertex(vertices[j], Wolf);
                            qVertex.push(vertex);
                        }
                        selectedV[vertices[j]] = SelectedBoth;
                    }
                }
            }
            if (vi.state == Wolf) {
                for (int j = 0; j <= iRi; ++j) {
                    if (vertices[j] <= ri) {
                        if (selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedHumance) {
                            Vertex vertex = initVertex(vertices[j], Wolf);
                            qVertex.push(vertex);
                            if (vertices[j]>= li) {
                                selectedV[vertices[j]] = SelectedWolf;
                            } else if (vertices[j] < li) {
                                selectedV[vertices[j]] = SelectedBoth;
                            }
                        }
                    }
                }
            }
        }
        
    }
    return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'int findIndex(std::vector<int>, int)':
werewolf.cpp:40:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if (yi > pathi[left] && left < pathi.size() - 1) {
      |                             ~~~~~^~~~~~~~~~~~~~~~~~
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:119:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |                 for (int j = iRi; j < path[vi.index].size(); ++j) {
      |                                   ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51