Submission #81516

#	Time	Username	Problem	Language	Result	Execution time	Memory
81516		zubec	Werewolf (IOI18_werewolf)	C++14	0 / 100	592 ms	27572 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 getRMn(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (mid <= pos){
        return getRMn(v+v+1, mid+1, r, pos, x);
    }
    if (t[0][v+v] < x){
        return getRMn(v+v, l, mid, pos, x);
    }
    return getRMn(v+v+1, mid+1, r, pos, x);
}
int getLMn(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (pos <= mid+1)
        return getLMn(v+v, l, mid, pos, x);
    if (t[0][v+v+1] < x)
        return getLMn(v+v+1, mid+1, r, pos, x);
    return getLMn(v+v, l, mid, pos, x);
}

int getRMx(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (mid <= pos){
        return getRMx(v+v+1, mid+1, r, pos, x);
    }
    if (t[1][v+v] > x){
        return getRMx(v+v, l, mid, pos, x);
    }
    return getRMx(v+v+1, mid+1, r, pos, x);
}
int getLMx(int v, int l, int r, int pos, int x){
    if (l == r){
        return l;
    }
    int mid = (l+r)>>1;
    if (pos <= mid+1)
        return getLMx(v+v, l, mid, pos, x);
    if (t[1][v+v+1] > x)
        return getLMx(v+v+1, mid+1, r, pos, x);
    return getLMx(v+v, l, mid, pos, x);
}

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, pos[s], l);
        int y1 = getRMn(1, 0, N-1, pos[s], l);
        int x2 = getLMx(1, 0, N-1, pos[e], r);
        int y2 = getRMx(1, 0, N-1, pos[e], r);
        if (a[x1] < l)
            ++x1;
        if (a[y1] < l)
            --y1;
        if (a[x2] > r)
            ++x2;
        if (a[y2] > r)
            --y2;
        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 1 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:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:95:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[cur].size(); j++){
                         ~~^~~~~~~~~~~~~~~
werewolf.cpp:106: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