Submission #611922

#	Time	Username	Problem	Language	Result	Execution time	Memory
611922		fvogel499	Werewolf (IOI18_werewolf)	C++17	0 / 100	318 ms	94688 KiB

werewolf

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

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

using namespace std;

const int inf = 1e9;
const int p2 = 1<<18;

struct Segtree {
    Segtree() {
        t = new int [p2*2];
        for (int i = 0; i < p2*2; i++) t[i] = -inf;
    }
    ~Segtree() {
        delete [] t;
    }
    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> calc(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, bool sw = false) {
    vector<int> graph [n];
    for (int i = 0; i < sz(edgeX); i++) {
        graph[edgeX[i]].push_back(edgeY[i]);
        graph[edgeY[i]].push_back(edgeX[i]);
    }
    vector<int> path;
    for (int i = 0; i < n; i++) if (sz(graph[i]) == 1) {
        bool vis [n];
        for (int j = 0; j < n; j++) vis[j] = false;
        int x = i;
        while (1) {
            vis[x] = true;
            path.push_back(x);
            bool ch = false;
            for (int y : graph[x]) if (!vis[y]) {
                x = y;
                ch = true;
                break;
            }
            if (!ch) {
                break;
            }
        }
        break;
    }
    assert(sz(path) == n);
    if (sw) {
        reverse(path.begin(), path.end());
    }
    int invPath [n];
    for (int i = 0; i < n; i++) invPath[path[i]] = i;
    const int nbQ = sz(queryX);
    for (int i = 0; i < nbQ; i++) {
        queryX[i] = invPath[queryX[i]];
        queryY[i] = invPath[queryY[i]];
    }
    vector<int> queriesSmallerThan [n];
    int latestPerQuery [nbQ];
    vector<int> queriesBiggerThan [n];
    int earliestPerQuery [nbQ];
    for (int i = 0; i < nbQ; i++) {
        if (queryLB[i] >= 1) {
            queriesSmallerThan[queryLB[i] - 1].push_back(i);
        }
        else {
            latestPerQuery[i] = -1;
        }
        if (queryRB[i]+1 < n) {
            queriesBiggerThan[queryRB[i] + 1].push_back(i);
        }
        else {
            earliestPerQuery[i] = n;
        }
    }
    Segtree st = Segtree();
    for (int i = 0; i < n; i++) {
        st.upd(invPath[i], invPath[i]);
        for (int j : queriesSmallerThan[i]) {
            latestPerQuery[j] = st.get(queryX[j], queryY[j]);
        }
    }
    st = Segtree();
    for (int i = n-1; i >= 0; i--) {
        st.upd(invPath[i], -invPath[i]);
        for (int j : queriesBiggerThan[i]) {
            earliestPerQuery[j] = -st.get(queryX[j], queryY[j]);
        }
    }
    vector<int> res(nbQ);
    vector<int> askPref [nbQ];
    for (int i = 0; i < nbQ; i++) {
        if (queryX[i] > queryY[i]) {
            res[i] = -1;
        }
        else {
            res[i] = 0;
            int x = min(earliestPerQuery[i]-1, n-1);
            assert(0 <= x && x < n);
            askPref[x].push_back(i);
        }
    }
    st = Segtree();
    for (int i = 0; i < n; i++) {
        st.upd(path[i], i);
        for (int j : askPref[i]) {
            int loc = st.get(queryLB[j], queryRB[j]);
            if (loc >= latestPerQuery[j]+1) {
                res[j] = 1;
            }
            else {
                res[j] = -1;
            }
        }
    }
    return res;
}

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) {
    vector<int> resA = calc(n, edgeX, edgeY, queryX, queryY, queryLB, queryRB, false);
    vector<int> resB = calc(n, edgeX, edgeY, queryX, queryY, queryLB, queryRB, true);
    vector<int> merge(size(resA));
    for (int i = 0; i < size(resA); i++) {
        if (resA[i] != -1) {
            assert(resB[i] == -1);
            merge[i] = resA[i];
        }
        else {
            assert(resB[i] != -1);
            merge[i] = resB[i];
        }
    }
    return merge;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> calc(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, bool)':
werewolf.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     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:2:
werewolf.cpp:71:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   71 |     assert(sz(path) == n);
      |                     ^
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:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int i = 0; i < size(resA); i++) {
      |                     ~~^~~~~~~~~~~~

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