oj.uz

Submission #82746

# Submission time Handle Problem Language Result Execution time Memory
82746 2018-11-01T14:47:53 Z zubec Werewolf (IOI18_werewolf) C++14
34 / 100
 957 ms 60432 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 tl = 0, tr = pos[s];
        int x1, y1, x2, y2;
        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;
        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

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 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5112 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 863 ms 55236 KB Output is correct
2 Correct 737 ms 59976 KB Output is correct
3 Correct 729 ms 59992 KB Output is correct
4 Correct 772 ms 60096 KB Output is correct
5 Correct 886 ms 60096 KB Output is correct
6 Correct 957 ms 60096 KB Output is correct
7 Correct 935 ms 60096 KB Output is correct
8 Correct 755 ms 60208 KB Output is correct
9 Correct 488 ms 60208 KB Output is correct
10 Correct 541 ms 60240 KB Output is correct
11 Correct 550 ms 60240 KB Output is correct
12 Correct 527 ms 60240 KB Output is correct
13 Correct 787 ms 60240 KB Output is correct
14 Correct 762 ms 60240 KB Output is correct
15 Correct 765 ms 60432 KB Output is correct
16 Correct 789 ms 60432 KB Output is correct
17 Correct 860 ms 60432 KB Output is correct

Subtask #4
0 / 51.0

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