Submission #82714

#	Time	Username	Problem	Language	Result	Execution time	Memory
82714		zubec	Werewolf (IOI18_werewolf)	C++14	0 / 100	645 ms	36076 KiB

werewolf

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

const int N = 200100;

vector <int> g[N];

int a[N], pos[N], t[2][N*4];

void update(int v, int l, int r, int pos, int x){
    if (l == r){
        t[0][v] = x;
        t[1][v] = x;
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid)
        update(v+v, l, mid, pos, x); else
        update(v+v+1, mid+1, r, pos, x);
    t[0][v] = min(t[0][v+v], t[0][v+v+1]);
    t[1][v] = max(t[1][v+v], t[1][v+v+1]);
}

int getMn(int v, int l, int r, int tl, int tr){
    if (l > r || tl > r || l > tr || tl > tr)
        return 1e9;
    if (tl <= l && r <= tr){
        return t[0][v];
    }
    int mid = (l+r)>>1;
    return min(getMn(v+v, l, mid, tl, tr), getMn(v+v+1, mid+1, r, tl, tr));
}

int getMx(int v, int l, int r, int tl, int tr){
    if (l > r || tl > r || l > tr || tl > tr)
        return 0;
    if (tl <= l && r <= tr){
        return t[1][v];
    }
    int mid = (l+r)>>1;
    return max(getMx(v+v, l, mid, tl, tr), getMx(v+v+1, mid+1, r, tl, tr));
}

int getRMn(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr || tl > tr)
        return -1;
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;

    int pos = -1;
    if (t[0][v+v] < x)
        pos = getRMn(v+v, l, mid, tl, tr, x);
    if (pos == -1 && t[0][v+v+1] < x)
        pos = getRMn(v+v+1, mid+1, r, tl, tr, x);
    return pos;
}

int getLMn(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr || tl > tr)
        return -1;
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    int pos = -1;
    if (t[0][v+v+1] < x)
        pos = getLMn(v+v+1, mid+1, r, tl, tr, x);
    if (pos == -1 && t[0][v+v] < x)
        pos = getLMn(v+v, l, mid, tl, tr, x);
    return pos;
}

int getRMx(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr || tl > tr)
        return -1;
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    int pos = -1;
    if (t[1][v+v] > x)
        pos = getRMx(v+v, l, mid, tl, tr, x);
    if (pos == -1 && t[1][v+v+1] > x)
        pos = getRMn(v+v+1, mid+1, r, tl, tr, x);
    return pos;
}
int getLMx(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr || tl > tr)
        return -1;
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    int pos = -1;
    if (t[1][v+v+1] > x)
        pos = getLMx(v+v+1, mid+1, r, tl, tr, x);
    if (pos == -1 && t[1][v+v] > x)
        pos = getLMx(v+v, l, mid, tl, tr, x);
    return pos;
}

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) {
    for (int i = 0; i < N; i++){
        g[i].clear();
    }
    for (int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    int cur = 0;
    for (int i = 0; i < N; i++){
        if (g[i].size() == 1){
            cur = i;
            break;
        }
    }
    int prev = -1;
    for (int i = 0; i < N; i++){
        pos[cur] = i;
        a[i] = cur;
        update(1, 0, N-1, i, cur);
        for (int j = 0; j < g[cur].size(); j++){
            int to = g[cur][j];
            if (to == prev)
                continue;
            prev = cur;
            cur = to;
            break;
        }
    }

    vector <int> A;
    for (int ii = 0; ii < S.size(); ii++){
        int s = S[ii], e = E[ii];
        int l = L[ii], r = R[ii];

        int x1 = getLMn(1, 0, N-1, 0, pos[s], l);
        int y1 = getRMn(1, 0, N-1, pos[s], N-1, l);
        int x2 = getLMx(1, 0, N-1, 0, pos[e], r);
        int y2 = getRMx(1, 0, N-1, pos[e], N-1, r);
        if (x1 == -1)
            x1 = 0;
        if (y1 == -1)
            y1 = N-1;
        if (x2 == -1)
            x2 = 0;
        if (y2 == -1)
            y2 = N-1;
        /*int x1, y1, x2, y2;
        int tl = 0, tr = pos[s];
        while(tl < tr){
            int mid = (tl+tr)>>1;
            if (getMn(1, 0, N-1, mid, pos[s]) < l)
                tl = mid+1; else
                tr = mid;
        }
        x1 = tl;
        tl = pos[s], tr = N-1;
        while(tl < tr){
            int mid = (tl+tr+1)>>1;
            if (getMn(1, 0, N-1, pos[s], mid) < l)
                tr = mid-1; else
                tl = mid;
        }
        y1 = tl;
        tl = 0, tr = pos[e];
        while(tl < tr){
            int mid = (tl+tr)>>1;
            if (getMx(1, 0, N-1, mid, pos[e]) > r)
                tl = mid+1; else
                tr = mid;
        }
        x2 = tl;
        tl = pos[e], tr = N-1;
        while(tl < tr){
            int mid = (tl+tr+1)>>1;
            if (getMx(1, 0, N-1, pos[e], mid) > r)
                tr = mid-1; else
                tl = mid;
        }
        y2 = tl;*/

        int bb = 0;
        //cout << "kek " << x1 << ' ' << y1 << "  " << x2 << ' ' << y2 << endl;
        int x3 = max(x1, x2);
        int y3 = min(y1, y2);
        if (x3 <= y3)
            bb = 1;

        A.push_back(bb);
    }

    return A;

}

/**

5 4 1
1 0
0 3
3 4
4 2
1 2 0 3

*/

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:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:125:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[cur].size(); j++){
                         ~~^~~~~~~~~~~~~~~
werewolf.cpp:136:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < S.size(); ii++){
                      ~~~^~~~~~~~~~

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