Submission #766854

#	Time	Username	Problem	Language	Result	Execution time	Memory
766854		birktj	Werewolf (IOI18_werewolf)	C++14	Compilation error	0 ms	0 KiB

werewolf

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

typedef vector<int> vi;

constexpr int MAXN = 2000000;
constexpr int INF = 1000000000;

template<class T, T e, class O>
class SegmentTree {
    int N;
    int off;
    vector<T> v;
public:
    SegmentTree(vector<T> initial) {
        int n = initial.size();
        N = 1;
        while (N < n+2) N *= 2;
        off = N+1;
        N *= 2;

        v = vector<T>(N, e);
        
        for (int i = 0; i < n; i++)
            v[off+i] = initial[i];

        for (int i = off-1; i > 0; i--)
            v[i] = O{}(v[i*2], v[i*2+1]);
    }

    T get(int l, int r) {
        l += off-1;
        r += off+1;

        T lv = e;
        T rv = e;
        
        while (l/2 != r/2) {
            if (l % 2 == 0) lv = O{}(lv, v[l+1]);
            if (r % 2 == 1) rv = O{}(v[r-1], rv);
            l /= 2;
            r /= 2;
        }

        return O{}(lv, rv);
    }

    void update(int i, T n) {
        i += off;
        v[i] = n;
        i /= 2;

        while (i > 0) {
            v[i] = O{}(v[i*2], v[i*2+1]);
            i /= 2;
        }
    }
};

struct Min {
    int operator() (int a, int b) {
        return min(a, b);
    }
};

struct Max {
     int operator() (int a, int b) {
        return max(a, b);
    }
};

class UF {
    vector<int> p;
public:
    UF(int n) : p(n) {
        for (int i = 0; i < n; i++)
            p[i] = i;
    }

    int find(int i) {
        return p[i] == i ? i : p[i] = find(p[i]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        p[b] = a;
    }
};

int binary_search(function<bool(int)> P, int a, int b) {
    while (a < b) {
        int m = (a + b) / 2;
        if (P(m)) b = m;
        else a = m+1;
    }

    return a;
}

void euler_path(vi &out, vi G[], int LP[], int RP[], int u) {
    LP[u] = out.size();
    out.push_back(u);
    //cerr << "visiting: " << u << endl;
    for (int v : G[u]) {
        euler_path(out, G, LP, RP, v);
        out.push_back(u);
    }
    RP[u] = out.size() - 1;
}

int N, Q, SLP[MAXN], SRP[MAXN], ELP[MAXN], ERP[MAXN];
vi G[MAXN], ST[MAXN], ET[MAXN];

vector<int> check_validity(int n, vi x, vi y, vi S, vi E, vi L, vi R) {
    N = n;
    Q = S.size();
    for (int i = 0; i < x.size(); i++) {
        G[x[i]].push_back(y[i]);
        G[y[i]].push_back(x[i]);
    }

    //cerr << "starting tree generation" << endl;

    UF s_uf(n);
    for (int i = n-1; i >= 0; i--) {
        for (int j : G[i]) if (j > i && s_uf.find(i) != s_uf.find(j)) {
            ST[i].push_back(s_uf.find(j));
            s_uf.unite(i, j);
        }
    }

    UF e_uf(n);
    for (int i = 0; i < n; i++) {
        for (int j : G[i]) if (j < i && e_uf.find(i) != e_uf.find(j)) {
            ET[i].push_back(e_uf.find(j));
            e_uf.unite(i, j);
        }
    }

    //cerr << "starting euler_path" << endl;

    vi s_seg;
    vi e_seg;
    euler_path(s_seg, ST, SLP, SRP, 0);
    euler_path(e_seg, ET, ELP, ERP, n-1);

    SegmentTree<int, INF, Min> s_tree(s_seg);
    SegmentTree<int, 0, Max> e_tree(e_seg);

    cerr << "s_seg: " << endl;
    for (int x : s_seg)
        cerr << x << " ";
    cerr << endl;

    cerr << "e_seg: " << endl;
    for (int x : e_seg)
        cerr << x << " ";
    cerr << endl;
        
    vi A(Q);
    for (int i = 0; i < Q; i++) {
        int s = S[i], e = E[i], l = L[i], r = R[i];
        
        int s_l = binary_search([&](int i) {return s_tree.get(i, SLP[s]) >= l;}, 0, SLP[s]);
        int s_r = binary_search([&](int i) {return s_tree.get(SRP[s], i) < l;}, SRP[s], s_seg.size()-1) - 1;
        if (s_tree.get(SRP[s], s_r+1) >= l) s_r++;
         
        int e_l = binary_search([&](int i) {return e_tree.get(i, ELP[e]) <= r;}, 0, ELP[e]);
        int e_r = binary_search([&](int i) {return e_tree.get(ERP[e], i) > r;}, ERP[e], e_seg.size()-1) - 1;
        if (e_tree.get(ERP[s], e_r+1) <= r) e_r++;

        /*
        cerr << "s = " << s << " e = " << e << " l = " << l << " r = " << r << endl;

        cerr << "slp: " << SLP[s] << " srp: " << SRP[s] << endl;
        cerr << "elp: " << ELP[e] << " erp: " << ERP[e] << endl;

        //cerr << "s_tree.get(0, slp) = " << s_tree.get(0, SLP[s]) << endl;

        cerr << "s_l = " << s_l << " s_r = " << s_r << endl;

        cerr << "e_l = " << e_l << " e_r = " << e_r << endl;
        */
            
        if (ELP[s_seg[s_l]] >= e_l && ERP[s_seg[s_r]] <= e_r)
            A[i] = 1;
        else if (SLP[e_seg[e_l]] >= s_l && SRP[e_seg[e_l]] <= s_r)
            A[i] = 1;
        else
            A[i] = 0;
    }

    return A;
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vi x(m), y(m), s(q), e(q), l(q), r(q);

    for (int i = 0; i < m; i++)
        cin >> x[i] >> y[i];

    for (int i = 0; i < q; i++)
        cin >> s[i] >> e[i] >> l[i] >> r[i];

    vi a = check_validity(n, x, y, s, e, l, r);

    for (int i = 0; i < q; i++)
        cout << a[i] << endl;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < x.size(); i++) {
      |                     ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccMMUAhx.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgogg6x.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status