Submission #1018775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018775		otarius	Werewolf (IOI18_werewolf)	C++17	0 / 100	402 ms	97648 KiB

werewolf

// #include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
 
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long
 
// #define int long long
// #define int unsigned long long
 
const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;
const int maxN = 2e5 + 15;
const int lg = 21;
 
// namespace {

// int read_int() {
//   int x;
//   if (scanf("%d", &x) != 1) {
//     fprintf(stderr, "Error while reading input\n");
//     exit(1);
//   }
//   return x;
// }

// }  // namespace

vector<int> g[maxN], adj[maxN][2], vc; vector<pair<pii, pii>> qs[maxN];
int n, par[maxN][2], p[maxN][lg][2], in[maxN][2], out[maxN][2], tim, t[4 * maxN];
void update(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        t[v] = val;
        return;
    } int tm = (tl + tr) / 2;
    if (pos <= tm) update(2 * v, tl, tm, pos, val);
    else update(2 * v + 1, tm + 1, tr, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
int getmax(int v, int tl, int tr, int l, int r) {
    if (l > r) return -inf;
    if (tl == l && tr == r) return t[v];
    int tm = (tl + tr) / 2;
    return max(getmax(2 * v, tl, tm, l, min(r, tm)),
               getmax(2 * v + 1, tm + 1, tr, max(l, tm + 1), tr));
}
void make_set() {
    for (int i = 1; i <= n; i++) {
        par[i][0] = par[i][1] = i;
        p[i][0][0] = p[i][0][1] = i;
    }
}
int find_set(int v, int f) {
    if (par[v][f] == v)
        return v;
    return par[v][f] = find_set(par[v][f], f);
}
void union_set(int x, int y, int f) {
    int rx = find_set(x, f), ry = find_set(y, f);
    if (rx != ry) {
        par[ry][f] = rx;
        p[ry][0][f] = x;
    }
}
void dfs(int v, int f) {
    if (f) vc.pb(v);
    in[v][f] = ++tim;
    for (int u : adj[v][f]) dfs(u, f);
    out[v][f] = tim;
}
int left_lift(int val, int x) {
    for (int i = lg - 1; i >= 0; i--)
        if (p[x][i][1] >= val) x = p[x][i][1];
    return x;
}
int right_lift(int val, int x) {
    for (int i = lg - 1; i >= 0; i--)
        if (p[x][i][0] <= val) x = p[x][i][0];
    return x;
}
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;
    for (int i = 0; i < x.size(); i++) {
        x[i]++; y[i]++;
        g[x[i]].pb(y[i]);
        g[y[i]].pb(x[i]);
    } make_set();
    for (int i = 1; i <= n; i++)
        for (int j : g[i]) if (j < i) union_set(i, j, 0);
    for (int i = n; i >= 1; i--)
        for (int j : g[i]) if (j > i) union_set(i, j, 1);
    for (int i = 1; i <= n; i++) {
        if (p[i][0][0] != i) adj[p[i][0][0]][0].pb(i);
        if (p[i][0][1] != i) adj[p[i][0][1]][1].pb(i);
    } for (int i = 1; i < lg; i++) {
        for (int j = 1; j <= n; j++) {
            p[j][i][0] = p[p[j][i - 1][0]][i - 1][0];
            p[j][i][1] = p[p[j][i - 1][1]][i - 1][1];
        }
    } dfs(n, 0); tim = 0; dfs(1, 1);
    vector<int> ans; ans.resize(s.size());
    for (int i = 0; i < s.size(); i++) {
        s[i]++; e[i]++; l[i]++; r[i]++;
        int rl = left_lift(l[i], s[i]);
        int rr = right_lift(r[i], e[i]);
        qs[out[rl][1]].pb({{i, in[rl][1]}, {in[rr][0], out[rr][0]}});
    } for (int i = 1; i <= n; i++) {
        update(1, 1, n, in[vc[i - 1]][0], i);
        for (auto v : qs[i]) {
            ans[v.ff.ff] = (getmax(1, 1, n, v.sc.ff, v.sc.sc) >= v.ff.sc);
        }
    } return ans;
}
// int main() {
//   int N = read_int();
//   int M = read_int();
//   int Q = read_int();
//   std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
//   for (int j = 0; j < M; ++j) {
//     X[j] = read_int();
//     Y[j] = read_int();
//   }
//   for (int i = 0; i < Q; ++i) {
//     S[i] = read_int();
//     E[i] = read_int();
//     L[i] = read_int();
//     R[i] = read_int();
//   }

//   std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
//   for (size_t i = 0; i < A.size(); ++i) {
//     printf("%d\n", A[i]);
//   }
//   return 0;
// }

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:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < x.size(); i++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

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