Submission #621331

#	Time	Username	Problem	Language	Result	Execution time	Memory
621331		Jomnoi	Werewolf (IOI18_werewolf)	C++17	15 / 100	1209 ms	63872 KiB

werewolf

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

const int MAX_N = 2e5 + 5;

int N, M, Q;
vector <int> graph[MAX_N];
bool visited[MAX_N][2];
vector <int> order;
int enpos[MAX_N];
int tmax[MAX_N][20], tmin[MAX_N][20];

int getMin(int l, int r) {
    int j = log2(r - l + 1);
    return min(tmin[l][j], tmin[r - (1<<j) + 1][j]);
}

int getMax(int l, int r) {
    int j = log2(r - l + 1);
    return max(tmax[l][j], tmax[r - (1<<j) + 1][j]);
}

void dfs(int u, int p) {
    order.push_back(u);
    for(auto v : graph[u]) {
        if(v != p) {
            dfs(v, u);
        }
    }
}

vector <int> check_validity(int n, vector <int> X, vector <int> Y, vector <int> S, vector <int> E, vector <int> L, vector <int> R) {
    N = n, Q = S.size(), M = X.size();
    vector <int> answer(Q, 0);
    for(int i = 0; i < M; i++) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    if(N <= 3000 and M <= 6000 and Q <= 3000) {
        for(int qq = 0; qq < Q; qq++) {
            int s = S[qq], e = E[qq], l = L[qq], r = R[qq];
            for(int i = 0; i < N; i++) {
                visited[i][0] = false;
                visited[i][1] = false;
            }

            queue <pair <int, int>> q;
            if(s >= l) {
                q.emplace(s, 0);
                visited[s][0] = true;
            }
            while(!q.empty()) {
                auto [u, k] = q.front();
                q.pop();

                if(k == 0 and l <= u and u <= r and visited[u][1] == false) {
                    visited[u][1] = true;
                    q.emplace(u, 1);
                }
                for(auto v : graph[u]) {
                    if(k == 0) {
                        if(v >= l and visited[v][0] == false) {
                            visited[v][0] = true;
                            q.emplace(v, 0);
                        }
                    }
                    else {
                        if(v <= r and visited[v][1] == false) {
                            visited[v][1] = true;
                            q.emplace(v, 1);   
                        }
                    }
                }
            }

            answer[qq] = visited[e][1];
        }
    }
    else {
        for(int i = 0; i < N; i++) {
            if(graph[i].size() == 1) {
                dfs(i, -1);
                break;
            }
        }
        for(int i = 0; i < N; i++) {
            enpos[order[i]] = i;
            tmin[i][0] = order[i];
            tmax[i][0] = order[i];
        }
        for(int j = 1; j < 20; j++) {
            for(int i = 0; i + (1<<j) - 1 < N; i++) {
                tmin[i][j] = min(tmin[i][j - 1], tmin[i + (1<<(j - 1))][j - 1]);
                tmax[i][j] = max(tmax[i][j - 1], tmax[i + (1<<(j - 1))][j - 1]);
            }
        }

        for(int qq = 0; qq < Q; qq++) {
            int s = S[qq], e = E[qq], ll = L[qq], rr = R[qq];
            int l, r, mid, sR, sL, eR, eL;
 
            l = 0, r = enpos[order[s]];
            while(l <= r) {
                mid = (l + r) / 2;

                if(getMin(mid, enpos[order[s]]) >= ll) {
                    r = mid - 1;
                    sL = mid;
                }
                else {
                    l = mid + 1;
                }
            }
            l = enpos[order[s]], r = N - 1;
            while(l <= r) {
                mid = (l + r) / 2;

                if(getMin(enpos[order[s]], mid) >= ll) {
                    l = mid + 1;
                    sR = mid;
                }
                else {
                    r = mid - 1;
                }
            }
            l = 0, r = enpos[order[e]];
            while(l <= r) {
                mid = (l + r) / 2;

                if(getMax(mid, enpos[order[e]]) <= rr) {
                    r = mid - 1;
                    eL = mid;
                }
                else {
                    l = mid + 1;
                }
            }
            l = enpos[order[e]], r = N - 1;
            while(l <= r) {
                mid = (l + r) / 2;
                
                if(getMax(enpos[order[e]], mid) <= rr) {
                    l = mid + 1;
                    eR = mid;
                }
                else {
                    r = mid - 1;
                }
            }

            if((sR - sL + 1) + (eR - eL + 1) > (max(sR, eR) - min(sL, eL) + 1)) {
                answer[qq] = 1;
            }
        }
    }
    return answer;
}

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:102:36: warning: 'eR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |             int l, r, mid, sR, sL, eR, eL;
      |                                    ^~
werewolf.cpp:102:40: warning: 'eL' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |             int l, r, mid, sR, sL, eR, eL;
      |                                        ^~
werewolf.cpp:102:28: warning: 'sR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |             int l, r, mid, sR, sL, eR, eL;
      |                            ^~
werewolf.cpp:102:32: warning: 'sL' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |             int l, r, mid, sR, sL, eR, eL;
      |                                ^~

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