Submission #82745

#	Time	Username	Problem	Language	Result	Execution time	Memory
82745		zubec	Werewolf (IOI18_werewolf)	C++14	34 / 100	874 ms	184344 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][20][N], n, st[N];

void build(){
    st[1] = 0;
    for (int i = 2; i <= n; i++)
        st[i] = st[i/2] + 1;
    for (int i = 0; i < n; i++){
        t[0][0][i] = t[1][0][i] = a[i];
    }
    for (int i = 1; i <= st[n]; i++){
        for (int j = 0; j < n-(1<<i)+1; j++){
            t[0][i][j] = min(t[0][i-1][j], t[0][i-1][j+(1<<(i-1))]);
            t[1][i][j] = max(t[1][i-1][j], t[1][i-1][j+(1<<(i-1))]);
        }
    }
}

int getMn(int l, int r){
    int sz = st[(r-l+1)];
    return min(t[0][sz][l], t[0][sz][r-(1<<sz)+1]);
}

int getMx(int l, int r){
    int sz = st[(r-l+1)];
    return max(t[1][sz][l], t[1][sz][r-(1<<sz)+1]);
}

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) {
    n = N;
    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;
        for (int j = 0; j < g[cur].size(); j++){
            int to = g[cur][j];
            if (to == prev)
                continue;
            prev = cur;
            cur = to;
            break;
        }
    }
    build();
    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, y1, x2, y2;
        int tl = 0, tr = pos[s];
        while(tl < tr){
            int mid = (tl+tr)>>1;
            if (getMn(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(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(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(pos[e], mid) > r)
                tr = mid-1; else
                tl = mid;
        }
        y2 = tl;

        int bb = 0;
        //cout << "kek " << x1 << ' ' << y1 << "  " << x2 << ' ' << y2 << endl;
        if ((pos[s] <= pos[e] && y1 >= x2) || (pos[e] <= pos[s] && y2 >= x1))
            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:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:56:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[cur].size(); j++){
                         ~~^~~~~~~~~~~~~~~
werewolf.cpp:67: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: 34 / 34
• Subtask 4: 0 / 51