Submission #1204054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204054		notme	Werewolf (IOI18_werewolf)	C++20	0 / 100	157 ms	61940 KiB

werewolf

#include <bits/stdc++.h>
#define pb push_back
#include "werewolf.h"
using namespace std;
const int maxn = 2e5 + 10;
int n, m, q;
vector < int > g[maxn];

struct query
{
    int l, r, s, e;
    query(){};
    query(int _l, int _r, int _s, int _e)
    {
        l = _l;
        r = _r;
        s = _s;
        e = _e;
    }
};

int t[maxn * 4];
int ql, qr;
int doquery(int i, int l, int r)
{
    if(qr < l || ql > r)return 0;
    if(ql <= l && r <= qr)return t[i];
    int mid = (l + r)/2;
    return doquery(2*i, l, mid) + doquery(2*i+1, mid+1, r);
}
int make_query(int queryl, int queryr)
{
    ql = queryl;
    qr = queryr;
    return doquery(1, 1, n);
}
int updpos, updval;
void update(int i, int l, int r)
{
    if(l == r)
    {
        t[i] = updval;
        return;
    }
    int mid = (l + r)/2;
    if(updpos <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = t[2*i] + t[2*i+1];
}
void make_update(int pos, int val)
{
    updpos = pos;
    updval = val;
    update(1, 1, n);
}
query ask[maxn];
vector < int > emax, emin;

int pos[maxn];
struct dsu_tree /// mintree -> pref, ends in n-1
{               /// maxtree -> suff, ends in 0
    int tmr;
    vector < int > p;
    vector < int > tin, tout;
    vector < vector < int > > adj;
    vector < vector < int > > jump;
    vector < int > used;
    dsu_tree(int n)
    {
        tmr = 0;
        used.resize(n, 0);
        p.resize(n);
        tin.resize(n);
        tout.resize(n);
        adj.resize(n);
        jump.resize(n);
        for (int i = 0; i < n; ++ i)
        {
            p[i] = i;
        }
    }
    /// dsu stuff
    int find_leader(int i)
    {
        if(p[i] == i)return i;
        return (p[i] == find_leader(p[i]));
    }

    void add_edge(int v, int type)
    {
        int leadv = find_leader(v);
        for (auto u: g[v])
        {
            if(u > v && type == 0)continue;
            if(u < v && type == 1)continue;
            if(type == 0)
            {
               // cout << "add " << u << " " << v << endl;
            }
            int leadu = find_leader(u);
            if(leadv == leadu)continue;
            if(type == 0)
            {
                //cout << v << " " << leadu << endl;
            }
            p[leadu] = leadv;
            adj[v].pb(leadu);
            adj[leadu].pb(v);
        }
    }
    /// euler stuff
    void euler(int beg, int from, bool type)
    {

        used[beg] = 1;
        //cout << beg << endl;
        jump[beg].resize(20);
        jump[beg][0] = from;

        for (int j = 1; j < 20; ++ j)
        {
            if(jump[beg][j-1] == -1)
            {
                jump[beg][j] = -1;
                continue;
            }
            jump[beg][j-1] = jump[jump[beg][j-1]][j-1];
        }
        tmr ++;
        tin[beg] = tmr;
        if(type)
            pos[beg] = tmr;
        if(type == 0)
            emin.pb(beg);
        else emax.pb(beg);
        for (auto nb: adj[beg])
        {
            if(used[nb])continue;
            euler(nb, beg, type);
        }
        tout[beg] = tmr;

    }
};
struct segm
{
    int lmax, rmax, lmin, rmin;
    segm(){};
    segm(int _lmax, int _rmax, int _lmin, int _rmin)
    {
        lmax = _lmax;
        rmax = _rmax;
        lmin = _lmin;
        rmin = _rmin;
    }
};

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R)
{
    n = N;
    m = L.size();
    q = S.size();
    for (int i = 0; i < X.size(); ++ i)
    {
        int from = X[i], to = Y[i];
        g[from].pb(to);
        g[to].pb(from);
    }
    for (int i = 0; i < m; ++ i)
    {
        ask[i] = query(L[i], R[i], S[i], E[i]);
    }
    dsu_tree mintree(n), maxtree(n);
    for (int i = 0; i < n; ++ i)
        mintree.add_edge(i, 0);
    for (int i = n-1; i >= 0; -- i)
        maxtree.add_edge(i, 1);
    mintree.euler(n-1, -1, 0);
    maxtree.euler(0, -1, 1);

    std::vector < int > ans;
    vector < segm > sg;
    ans.resize(q, 0);

    vector < vector < int > > st, fi;
    st.resize(n+1);
    fi.resize(n+1);
    for (int i = 0; i < m; ++ i)
    {
        int from = ask[i].s;
        int to = ask[i].e;
        for (int bit = 19; bit >= 0; -- bit)
        {
            if(maxtree.jump[from][bit] != -1 && maxtree.jump[from][bit] >= ask[i].l)
                from = maxtree.jump[from][bit];
        }
        for (int bit = 19; bit >= 0; -- bit)
        {
            if(mintree.jump[from][bit] != -1 && mintree.jump[from][bit] <= ask[i].r)
                to = mintree.jump[from][bit];
        }
       // cout << "real " << from << " " << to << endl;
        sg.pb(segm(maxtree.tin[from], maxtree.tout[from], mintree.tin[to], maxtree.tout[to]));
        /// from in maxtree, to in mintree
    }
    for (int i = 0; i < sg.size(); ++ i)
    {
        int lt = sg[i].lmin, rt = sg[i].rmin;
        fi[lt - 1].pb(i);
        st[rt].pb(i);
    }
    for (int i = 1; i <= n; ++ i)
    {
        make_update(pos[i], 1);
        for (auto &x: fi[i])
        {
            long long num = make_query(sg[x].lmax, sg[x].rmax);
            ans[x] -= num; //make_query(segm[x].lmax, segm[x].rmax);
        }
        for (auto &x: st[i])ans[x] += make_query(sg[x].lmax, sg[x].rmax);
    }
    return ans;
}

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