Submission #640475

#	Time	Username	Problem	Language	Result	Execution time	Memory
640475		ghostwriter	Werewolf (IOI18_werewolf)	C++14	0 / 100	666 ms	89256 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};
bool cmp(Edge &a, Edge &b) { return a.w < b.w; }
bool cmp1(Edge &a, Edge &b) { return a.w > b.w; }
struct Query {
    int s, e, l, id;
    Query() {}
    Query(int s, int e, int l, int id) : s(s), e(e), l(l), id(id) {}
};
const int N = 2e5 + 5;
int n, q, p[N], pos[N], mine[N][18], LOG[N];
vpi d[N];
multiset<int> s[N];
vector<Edge> e, e1;
vector<Query> query[N];
int getp(int x) { return x == p[x]? x : p[x] = getp(p[x]); }
void join(int x, int y, int w) {
    x = getp(x);
    y = getp(y);
    if (x == y) return;
    if (sz(d[x]) < sz(d[y])) swap(x, y);
    d[x].back().nd = w;
    EACH(i, d[y]) d[x].pb(i);
    d[y].clear();
    p[y] = x;
}
void join(int x, int y) {
    x = getp(x);
    y = getp(y);
    if (x == y) return;
    if (sz(s[x]) < sz(s[y])) swap(x, y);
    EACH(i, s[y]) s[x].insert(i);
    s[y].clear();
    p[y] = x;
}
int get(int l, int r) {
    if (l > r) swap(l, r);
    --r;
    int len = LOG[r - l + 1];
    return min(mine[l][len], mine[r - (1 << len) + 1][len]);
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    n = N;
    q = sz(S);
    vi ans(q, 0);
    int m = sz(X);
    FOR(i, 0, m - 1) {
        int u = X[i], v = Y[i], w = max(u, v), w1 = min(u, v);
        e.pb(Edge(u, v, w));
        e1.pb(Edge(u, v, w1));
    }
    FOR(i, 0, q - 1) {
        int s = S[i], e = E[i], l = L[i], r = R[i];
        query[r].pb(Query(s, e, l, i));
    }
    FOR(i, 0, n - 1) {
        p[i] = i;
        d[i].pb({i, i});
    }
    sort(all(e), cmp);
    sort(all(e1), cmp1);
    EACH(i, e1) {
        int u = i.u, v = i.v, w = i.w;
        join(u, v, w);
    }
    vpi a1 = d[getp(0)];
    FOR(i, 0, n - 1) {
        pos[a1[i].st] = i;
        mine[i][0] = a1[i].nd;
    }
    FOR(i, 1, n) LOG[i] = log2(i);
    FOR(j, 1, 17)
    FOR(i, 0, n - 1) {
        if (i + (1 << j) > n - 1) continue;
        int a = mine[i][j - 1], b = mine[i + (1 << (j - 1))][j - 1];
        mine[i][j] = min(a, b);
    }
    FOR(i, 0, n - 1) {
        p[i] = i;
        s[i].insert(pos[i]);
    }
    int l = 0;
    FOR(i, 0, n - 1) {
        WHILE(l < sz(e) && e[l].w <= i) {
            join(e[l].u, e[l].v);
            ++l;
        }
        EACH(j, query[i]) {
            int s = j.s, e = j.e, l = j.l, id = j.id;
            if (s <= i && e <= i) {
                if (s >= l) ans[id] = getp(s) == getp(e);
                continue;
            }
            if (s >= l && e >= l) {
                ans[id] = get(pos[s], pos[e]) >= l;
                continue;
            }
            if (s < e) continue;
            swap(s, e);
            int root = getp(s), maxr = -1;
            multiset<int> &s1 = ::s[root];
            if (*--s1.end() >= pos[e]) {
                int pos1 = pos[e], pos2 = *s1.lb(pos[e]);
                maxr = max(maxr, get(pos1, pos2));
                if (s1.lb(pos[e]) != s1.begin()) {
                    int pos2 = *--s1.lb(pos[e]);
                    maxr = max(maxr, get(pos1, pos2));
                }
            }
            else {
                int pos1 = pos[e], pos2 = *--s1.end();
                maxr = max(maxr, get(pos1, pos2));   
            }
            if (maxr >= l) ans[id] = 1;
        }
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message (stderr)

werewolf.cpp: In function 'void join(int, int, int)':
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
werewolf.cpp:63:5: note: in expansion of macro 'EACH'
   63 |     EACH(i, d[y]) d[x].pb(i);
      |     ^~~~
werewolf.cpp: In function 'void join(int, int)':
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
werewolf.cpp:72:5: note: in expansion of macro 'EACH'
   72 |     EACH(i, s[y]) s[x].insert(i);
      |     ^~~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:87:5: note: in expansion of macro 'FOR'
   87 |     FOR(i, 0, m - 1) {
      |     ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:92:5: note: in expansion of macro 'FOR'
   92 |     FOR(i, 0, q - 1) {
      |     ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:96:5: note: in expansion of macro 'FOR'
   96 |     FOR(i, 0, n - 1) {
      |     ^~~
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
werewolf.cpp:102:5: note: in expansion of macro 'EACH'
  102 |     EACH(i, e1) {
      |     ^~~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:107:5: note: in expansion of macro 'FOR'
  107 |     FOR(i, 0, n - 1) {
      |     ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:111:5: note: in expansion of macro 'FOR'
  111 |     FOR(i, 1, n) LOG[i] = log2(i);
      |     ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:112:5: note: in expansion of macro 'FOR'
  112 |     FOR(j, 1, 17)
      |     ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:113:5: note: in expansion of macro 'FOR'
  113 |     FOR(i, 0, n - 1) {
      |     ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:118:5: note: in expansion of macro 'FOR'
  118 |     FOR(i, 0, n - 1) {
      |     ^~~
werewolf.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
werewolf.cpp:123:5: note: in expansion of macro 'FOR'
  123 |     FOR(i, 0, n - 1) {
      |     ^~~
werewolf.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
werewolf.cpp:128:9: note: in expansion of macro 'EACH'
  128 |         EACH(j, query[i]) {
      |         ^~~~

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