Submission #399725

#	Time	Username	Problem	Language	Result	Execution time	Memory
399725		Jarif_Rahman	Werewolf (IOI18_werewolf)	C++17	0 / 100	1917 ms	267264 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int lim = 6e5;

struct persistent_segtree{
    struct node{
        ll sm;
        int l, r;
        node(){
            sm = 0LL;
            l = -1, r = -1;
        }
        node(ll _sm){
            sm = _sm;
            l = -1, r = -1;
        }
        node(ll _sm, int _l, int _r){
            l = _l, r = _r, sm = _sm;
        }
    };
    vector<node> v;
    int k;
    persistent_segtree(int n){
        k = 1;
        while(k <= n) k*=2; k*=2;
        v.resize(k, node(0));
        for(int i = 1; 2*i+1 < k; i++) v[i].l = 2*i, v[i].r = 2*i+1;
    }
    int upd(int nd, int a, int b, int in, ll x){
        if(a == b){
            v.pb(node(x));
            return (int)v.size() - 1;
        }
        int md = (a+b)/2;
        if(in <= md){
            int rt = upd(v[nd].l, a, md, in, x);
            v.pb(node(v[v[nd].r].sm+v[rt].sm, rt, v[nd].r));
            return (int)v.size()-1;
        }
        else{
            int rt = upd(v[nd].r, md+1, b, in, x);
            v.pb(node(v[v[nd].l].sm+v[rt].sm, v[nd].l, rt));
            return (int)v.size()-1;
        }
    }
    int upd(int nd, int in, ll x){
        return upd(nd, 0, k/2-1, in, x);
    }
    ll sum(int l, int r, int nd, int a, int b){
        if(a > r || b < l){
            return 0;
        }
        if(a >= l && b <= r){
            return v[nd].sm;
        }
        int md = (a+b)/2;
        return sum(l, r, v[nd].l, a, md) + sum(l, r, v[nd].r, md+1, b);
    }
    ll sum(int nd, int l, int r){
        return sum(l, r, nd, 0, k/2-1);
    }
};

struct reachability_tree{
    int n;
    vector<int> p;
    vector<vector<int>> v;
    vector<int> w;
    reachability_tree(int _n, int _w){
        n = _n;
        p.resize(n);
        v.resize(n);
        w.resize(n, _w);
        for(int i = 0; i < n; i++) p[i] = i;
    }
    inline int get(int x){
        if(p[x] != x) p[x] = get(p[x]);
        return p[x];
    }
    void unite(int a, int b, int _w){
        a = get(a), b = get(b);
        p[a] = n, p[b] = n;
        p.pb(n);
        v.pb({});
        v[n].pb(a);
        if(a != b) v[n].pb(b);
        w.pb(_w);
        n++;
    }
};

int n, m, q;

reachability_tree rtl(0, 0), rtr(0, 0);

int szl[lim], szr[lim], posl[lim], posr[lim];
vector<int> al, ar;
int ancl[lim][21], ancr[lim][21];

void dfsl(int nd, int ss){
    posl[nd] = al.size();
    if(rtl.v[nd].empty()){
        al.pb(nd);
        szl[nd] = 1;
        ancl[nd][1] = ss;
        return;
    }
    else szl[nd] =  0;
    for(int x: rtl.v[nd]) if(x != ss) dfsl(x, nd);
    for(int x: rtl.v[nd]) szl[nd]+=szl[x];
    ancl[nd][1] = ss;
}
void dfsr(int nd, int ss){
    posr[nd] = ar.size();
    if(rtr.v[nd].empty()){
        ar.pb(nd);
        szr[nd] = 1;
        ancr[nd][1] = ss;
        return;
    }
    else szr[nd] = 0;
    for(int x: rtr.v[nd]) if(x != ss) dfsr(x, nd);
    for(int x: rtr.v[nd]) szr[nd]+=szr[x];
    ancr[nd][1] = ss;
}

int get_anc_l(int nd, int ss){
    for(int i = 1; i < 21; i++){
        if(ss%2 == 1) nd = ancl[nd][i];
        if(nd == -1) return -1;
        ss/=2;
    }
    return nd;
}
int get_anc_r(int nd, int ss){
    for(int i = 1; i < 21; i++){
        if(ss%2 == 1) nd = ancr[nd][i];
        if(nd == -1) return -1;
        ss/=2;
    }
    return nd;
}

int bsl(int nd, int vl){
    int a = 0, b = 8e5;
    while(a < b){
        int md = (a+b+1)/2;
        int x = get_anc_l(nd, md);
        if(x == -1) x = 1e9;
        else x = rtl.w[x];
        if(x > vl) b = md-1;
        else a = md;
    }
    return get_anc_l(nd, a);
}
int bsr(int nd, int vl){
    int a = 0, b = 8e5;
    while(a < b){
        int md = (a+b+1)/2;
        int x  = get_anc_r(nd, md);
        if(x == -1) x = -1;
        else x = rtr.w[x];
        if(x < vl) b = md-1;
        else a = md;
    }
    return get_anc_r(nd, a);
}

vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> ss, vector<int> ee, vector<int> L, vector<int> R){
    ::n = n, m = U.size(), q = ss.size();
    pair<int, int> edgel[m], edger[m];
    for(int i = 0; i < m; i++)  edgel[i] = {U[i], V[i]}, edger[i] = {U[i], V[i]};

    sort(edgel, edgel+m, [&](pair<int, int> a, pair<int, int> b){
        return max(a.f, a.sc) < max(b.f, b.sc);
    });
    sort(edger, edger+m, [&](pair<int, int> a, pair<int, int> b){
        return min(a.f, a.sc) > min(b.f, b.sc);
    });

    rtl = reachability_tree(n, 0), rtr = reachability_tree(n, n+1);
    for(int i = 0; i < m; i++) rtl.unite(edgel[i].f, edgel[i].sc, max(edgel[i].f, edgel[i].sc)), rtr.unite(edger[i].f, edger[i].sc, min(edger[i].f, edger[i].sc));
    dfsl(rtl.n-1, -1);
    dfsr(rtr.n-1, -1);

    for(int i = 0; i < rtl.n; i++) ancl[i][0] = i;
    for(int i = 0; i < rtr.n; i++) ancr[i][0] = i;
    for(int i = 2; i < 21; i++) for(int j = 0; j < rtl.n; j++){
        if(ancl[j][i-1] == -1) continue;
        ancl[j][i] = ancl[ancl[j][i-1]][i-1];
    }
    for(int i = 2; i < 21; i++) for(int j = 0; j < rtr.n; j++){
        if(ancr[j][i-1] == -1) continue;
        ancr[j][i] = ancr[ancr[j][i-1]][i-1];
    }

    vector<int> ans(q, 0);

    pair<int, int> points[n];
    for(int i = 0; i < n; i++) points[i] = {posl[i], posr[i]};
    sort(points, points+n);


    vector<tuple<int, int, int, int>> query[n];
    int segterr_id[n];

    for(int qq = 0; qq < q; qq++){
        int ndl = bsl(ee[qq], R[qq]), ndr = bsr(ss[qq], L[qq]);
        int l1 = posl[ndl], r1 = posl[ndl]+szl[ndl]-1;
        int l2 = posr[ndr], r2 = posr[ndr]+szr[ndr]-1;
        query[max(l1, r1)].pb({min(l1, r1), min(l2, r2), max(l2, r2), qq});
    }

    persistent_segtree ps(n);
    int cur = 1, inx = 0;

    for(int i = 0; i < n; i++){
        while(inx < n && points[inx].f == i){
            cur = ps.upd(cur, points[inx].sc, ps.sum(cur, points[inx].sc, points[inx].sc)+1);
            inx++;
        }
        for(auto [l, r1, r2, in]: query[i]){
            l--;
            ll sum = ps.sum(cur, r1, r2);
            if(l >= 0) sum-=ps.sum(segterr_id[l], r1, r2);
            if(sum > 0) ans[in] = 1;
        }
        segterr_id[i] = cur;
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
werewolf.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
werewolf.cpp: In constructor 'persistent_segtree::persistent_segtree(int)':
werewolf.cpp:35:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   35 |         while(k <= n) k*=2; k*=2;
      |         ^~~~~
werewolf.cpp:35:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   35 |         while(k <= n) k*=2; k*=2;
      |                             ^

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