Submission #988890

#	Time	Username	Problem	Language	Result	Execution time	Memory
988890		Essa2006	Werewolf (IOI18_werewolf)	C++14	0 / 100	900 ms	349524 KiB

werewolf

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2015 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include<random>
#endif

//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)

const int N = 22, lg = 20, inf = 1e9;
int n, cur;
vector<int> SS;
vector<vector<int>> A;
vector<array<int, 2>> P, Anc, L, R, Dsc, Fin;
vector<vector<array<int, 2>>> Up;

int get(int id, int u, int v, int l, int r) {
    if (l > v || r < u) {
        return 0;
    }
    
    if (l >= u && r <= v) {
        return SS[id];
    }
    
    int md = (l + r) / 2;
    return get(id * 2, u, v, l, md) + get(id * 2 + 1, u, v, md + 1, r);
}

void update(int id, int c) {
    id += N;
    SS[id] += c;
    while (id /= 2) {
        SS[id] += c;
    }
}

int find(int ind, int id) {
    if (P[ind][id] == ind) {
        return ind;
    }

    return P[ind][id] = find(P[ind][id], id);
}

array<int, 2> cnt;
void merge(int a, int b, int id) {
    int ga = find(a, id), gb = find(b, id);
    if (ga == gb) {
        return ;
    }

    Anc[cnt[id]][id] = cur;
    L[cnt[id]][id] = ga, R[cnt[id]][id] = gb;
    Up[ga][0][id] = Up[gb][0][id] = P[ga][id] = P[gb][id] = cnt[id]++;

    return;
}

array<int, 2> time_;
void build(int u, int id) {
    Dsc[u][id] = time_[id]++;

    if (Up[u][0][id] == -1) {
        Up[u][0][id] = u;
    }
    for (int j = 1; j <= lg; j++) {
        Up[u][j][id] = Up[Up[u][j - 1][id]][j - 1][id];
    }

    if (u >= n) {
        build(L[u][id], id);
        build(R[u][id], id);
    }

    Fin[u][id] = time_[id]++;
}

int lca(int u, int c, int id) {
    for (int j = lg; j >= 0; j--) {
        if (Anc[Up[u][j][id]][id] <= c) {
            u = Up[u][j][id];
        }
    }
    return u;
}

vector<int> check_validity(int nn, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> LL, vector<int> RR) {
    n = nn;
    cnt[0] = cnt[1] = n;
    SS.resize(2 * N), A.resize(n), P.resize(2 * n), Anc.resize(2 * n, {inf, inf}), L.resize(2 * n, {-1, -1}), R.resize(2 * n, {-1, -1}), Dsc.resize(2 * n), Fin.resize(2 * n);
    Up.resize(2 * n, vector<array<int, 2>>(lg + 1, {-1, -1}));
    for (int i = 0; i < 2 * n; i++) {
        P[i][0] = P[i][1] = i;
    }


    for (int i = 0; i < X.size(); i++) {
        A[X[i]].push_back(Y[i]);
        A[Y[i]].push_back(X[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < A[i].size(); j++) {
            if (A[i][j] < i) {
                cur = i;
                merge(i, A[i][j], 0);
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < A[i].size(); j++) {
            if (A[i][j] > i) {
                cur =  n - 1 - i;
                merge(i, A[i][j], 1);
            }
        }
    }


    build(cnt[0] - 1, 0);
    build(cnt[1] - 1, 1);


    vector<int> Ans(LL.size());
    vector<vector<array<int, 3>>> All(4 * n); 
    vector<vector<int>> All2(4 * n);
    for (int i = 0; i < S.size(); i++) {
        int u = lca(E[i], RR[i], 0), v = lca(S[i], (n - 1) - LL[i], 1);
        
        All[Dsc[u][0]].push_back({i, Dsc[v][1], Fin[v][1]});
        All[Fin[u][0] + 1].push_back({-(i + 1), Dsc[v][1], Fin[v][1]});
        All2[Dsc[u][0] + 1].push_back(Dsc[u][1]);
    }
    vector<int> Prf(LL.size());
    for (int i = 0; i < 4 * n; i++) {
        for (int j = 0; j < All[i].size(); j++) {
            if (All[i][j][0] < 0) {
                All[i][j][0] *= -1;
                All[i][j][0]--;
                int res = get(1, All[i][j][1], All[i][j][2], 0, N - 1);
                res -= Prf[i];
                assert(res >= 0);
                if (res) {
                    Ans[All[i][j][0]] =1;
                }
            }
            else {
                Prf[All[i][j][0]] = get(1, All[i][j][1], All[i][j][2], 0, N - 1);
            }
        }
        for (int j = 0; j < All2[i].size(); j++) {
            update(All2[i][j], 1);
        }
    }

    return Ans;
}

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:216:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp:222:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         for (int j = 0; j < A[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
werewolf.cpp:230:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |         for (int j = 0; j < A[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
werewolf.cpp:246:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  246 |     for (int i = 0; i < S.size(); i++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp:255:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |         for (int j = 0; j < All[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
werewolf.cpp:270:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |         for (int j = 0; j < All2[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~

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