oj.uz

Submission #82745

# Submission time Handle Problem Language Result Execution time Memory
82745 2018-11-01T14:47:18 Z zubec Werewolf (IOI18_werewolf) C++14
34 / 100
 874 ms 184344 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 50484 KB Output is correct
2 Correct 686 ms 59108 KB Output is correct
3 Correct 684 ms 67568 KB Output is correct
4 Correct 769 ms 76092 KB Output is correct
5 Correct 827 ms 84292 KB Output is correct
6 Correct 786 ms 92892 KB Output is correct
7 Correct 874 ms 101424 KB Output is correct
8 Correct 668 ms 109656 KB Output is correct
9 Correct 469 ms 118024 KB Output is correct
10 Correct 568 ms 126588 KB Output is correct
11 Correct 541 ms 134988 KB Output is correct
12 Correct 482 ms 143540 KB Output is correct
13 Correct 783 ms 151072 KB Output is correct
14 Correct 744 ms 159492 KB Output is correct
15 Correct 864 ms 167536 KB Output is correct
16 Correct 781 ms 176040 KB Output is correct
17 Correct 868 ms 184344 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5084 KB Output isn't correct
2 Halted 0 ms 0 KB -