Submission #1015140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015140		deera	Werewolf (IOI18_werewolf)	C++14	0 / 100	3844 ms	524288 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;

deque<int> line;
int NUM;
map<int, vector<int>> roads;

vector<int> minT;
vector<int> maxT;

void build_minT(int n) {
    if (n >= NUM) {
        minT[n] = line[n - NUM];
        return;
    } else {
        build_minT(2 * n);
        build_minT(2 * n + 1);
        minT[n] = min(minT[2 * n], minT[2 * n + 1]);
    }
}

int query_minT(int a, int b) {
    if (a == b) return minT[a + NUM];
    if (a > b) return INT_MAX;

    a += NUM;
    b += NUM;
    int res = INT_MAX;
    while (a <= b) {
        if (a % 2 == 1) {
            res = min(res, minT[a]);
            a++;
        }
        if (b % 2 == 0) {
            res = min(res, minT[b]);
            b--;
        }
        a /= 2;
        b /= 2;
    }
    return res;
}

void build_maxT(int n) {
    if (n >= NUM) {
        maxT[n] = line[n - NUM];
        return;
    } else {
        build_maxT(2 * n);
        build_maxT(2 * n + 1);
        maxT[n] = max(maxT[2 * n], maxT[2 * n + 1]);
    }
}

int query_maxT(int a, int b) {
    if (a == b) return maxT[a + NUM];
    if (a > b) return INT_MIN;

    a += NUM;
    b += NUM;
    int res = INT_MIN;
    while (a <= b) {
        if (a % 2 == 1) {
            res = max(res, maxT[a]);
            a++;
        }
        if (b % 2 == 0) {
            res = max(res, maxT[b]);
            b--;
        }
        a /= 2;
        b /= 2;
    }
    return res;
}

void make_line(bool x) {
    if (x == true) {
        int last = line.back();
        vector<int> a = roads[last];

        if (a.size() == 1) {
            if (a[0] != line[line.size() - 2]) {
                line.push_back(a[0]);
            }
            make_line(false);
        } else {
            if (a[0] == line[line.size() - 2]) {
                line.push_back(a[1]);
                make_line(true);
            } else {
                line.push_back(a[0]);
                make_line(true);
            }
        }
    } else {
        int last = line.front();
        vector<int> a = roads[last];

        if (a.size() == 1) {
            line.push_front(a[0]);
            return;
        } else {
            if (a[0] == line[1]) {
                line.push_back(a[1]);
                make_line(false);
            } else {
                line.push_back(a[0]);
                make_line(false);
            }
        }
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    NUM = N;

    for(int i=1;i<=N;i++) {
        vector<int> a;
        roads[i] = a;
    }

    for(int i=0;i<X.size();i++) {
        roads[X[i]].push_back(Y[i]);
        roads[Y[i]].push_back(X[i]);
    }

    for (auto i: roads) {
        if (i.second.size() == 1) {
            line.push_back(i.first);
            line.push_back(i.second[0]);
            break;
        }
    }

    while (true) {
        vector<int> next = roads[line.back()];
        if (next.size() == 1) {
            break;
        } else {
            if (next[0] == line[line.size() - 2]) {
                line.push_back(next[1]);
            } else {
                line.push_back(next[0]);
            }
        }
    }


    minT.resize(2 * NUM);
    maxT.resize(2 * NUM);

    build_minT(1);
    build_maxT(1);

    vector<int> ans;

    for(int q=0;q<S.size();q++) {
        int s = S[q];
        int e = E[q];
        int l = L[q];
        int r = R[q];

        int mid = (s + e) / 2;
        while (true) {
            if (s >= e) {
                ans.push_back(1);
                break;
            }

            int minR = query_minT(s, mid);
            int maxR = query_maxT(mid + 1, e);

            if (minR <= l && maxR >= r) {
                ans.push_back(0);
            } else if (minR <= l) {
                e = mid;
                mid = (s + e) / 2;
            } else if (maxR >= r) {
                s = mid + 1;
                mid = (s + e) / 2;
            } else {
                ans.push_back(1);
                break;
            }
        }
    }

    return ans;
}

// int main() {
//     vector<int> a = check_validity(6, {1, 2, 3, 4, 5}, {2, 3, 4, 5, 6}, {1}, {2}, {1}, {2});

//     for(auto i: a) {
//         cout << i << endl;
//     }

// }

Compilation message (stderr)

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:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=0;i<X.size();i++) {
      |                 ~^~~~~~~~~
werewolf.cpp:158:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int q=0;q<S.size();q++) {
      |                 ~^~~~~~~~~

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