Submission #1205909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205909		notme	Werewolf (IOI18_werewolf)	C++20	15 / 100	1031 ms	216528 KiB

werewolf

#include <bits/stdc++.h>
#define pb push_back
#include "werewolf.h"
using namespace std;
const int maxn = 4e5 + 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;
    }
};
/// seg
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;


struct dsu_tree /// mintree -> pref, ends in n-1
{               /// maxtree -> suff, ends in 0
    int tmr, sz;
    vector < int > t, tp;
    vector < int > p;
    vector < int > tin, tout;
    vector < vector < int > > adj;
    vector < int > pos;
    vector < vector < int > > jump;
    vector < int > val;
    dsu_tree(int n)
    {
        tmr = 0;
        p.resize(2*n); /// dsu

        /// in reconstruction tree
        t.resize(2*n);
        tp.resize(n);
        adj.resize(2*n);
        val.resize(2*n);

        /// later on
        tin.resize(2*n);
        tout.resize(2*n);

        jump.resize(2*n);
        pos.resize(2*n);


        for (int i = 0; i < n; ++ i)
        {
            p[i] = i;
            t[i] = i;
            sz ++;
        }
    }
    /// dsu stuff
    int find_leader(int i)
    {
        if(p[i] == i)return i;
        return (find_leader(p[i]));
    }

    void add_edge(int v, int u, int w)
    {
       // cout << "adding edge " << v << " " << u << " with " << w << endl;
        int leadv = find_leader(v);
        int leadu = find_leader(u);
        if(leadv == leadu)return;
        p[leadu] = leadv;

        u = t[leadu];
        v = t[leadv];
        t[leadv] = sz;
        adj[sz].pb(v);
        adj[sz].pb(u);
        tp[u] = sz;
        tp[v] = sz;
        val[sz] = w;
        tp.pb(-1);
        sz ++;
    }
    /// euler stuff
    void euler(int beg, int from, bool type)
    {
        if(type == 0)
            emin.pb(beg);
        else emax.pb(beg);

        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] = jump[jump[beg][j-1]][j-1];
        }
        if(adj[beg].size() == 0)
        {
            tmr ++;
            tin[beg] = tmr-1;
            tout[beg] = tmr-1;
            pos[beg] = tmr-1;
            return;
        }
        tin[beg] = 1e9;
        tout[beg] = -1;
        for (auto nb: adj[beg])
        {
            if(nb == from)continue;
            euler(nb, beg, type);
            tin[beg] = min(tin[beg], tin[nb]);
            tout[beg] = max(tout[beg], tout[nb]);
        }


    }
};
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)
    {
        for (auto j: g[i])
        {
            if(j >= i)continue;
            mintree.add_edge(i, j, i);

        }
    }
    int szmin = mintree.sz;

    mintree.euler(szmin-1, -1, 0);
    for (int i = n-1; i >= 0; -- i)
    {
        for (auto j: g[i])
        {
            if(j <= i)continue;
            maxtree.add_edge(mintree.pos[i], mintree.pos[j], i);
        }
    }

   // int szmin = mintree.sz;
    int szmax = maxtree.sz;
   // mintree.euler(szmin-1, -1, 0);
    maxtree.euler(szmax-1, -1, 1);


   /* for (int i = 0; i < 2*n; ++ i)
        cout << mintree.tin[i] << " " << mintree.tout[i] << endl;
    cout << endl;
    for (int i = 0; i < 2*n; ++ i)
        cout << maxtree.tin[i] << " " << maxtree.tout[i] << endl;
    cout << endl;*/
    std::vector < int > ans;
    vector < segm > sg;
    ans.resize(q, 0);

    vector < vector < int > > st, fi;
    st.resize(2*n+1);
    fi.resize(2*n+1);
    for (int i = 0; i < q; ++ i)
    {
        int from = mintree.pos[ask[i].s];
        int to = ask[i].e;
        //cout << "* " << from << " " << to << endl;

        for (int bit = 19; bit >= 0; -- bit)
        {
            if(maxtree.jump[from][bit] != -1 && maxtree.val[maxtree.jump[from][bit]] >= ask[i].l)
                from = maxtree.jump[from][bit];
        }
        for (int bit = 19; bit >= 0; -- bit)
        {
            if(mintree.jump[to][bit] != -1 && mintree.val[mintree.jump[to][bit]] <= ask[i].r)
                to = mintree.jump[to][bit];
        }

        sg.pb(segm(maxtree.tin[from], maxtree.tout[from], mintree.tin[to], mintree.tout[to]));
        int lt = sg.back().lmin;
        int rt = sg.back().rmin;
        if(lt > 0)fi[lt - 1].pb(sg.size()-1);
        st[rt].pb(sg.size()-1);
    }

    for (int i = 0; i < n; ++ i)
    {
        make_update(maxtree.pos[i], 1);

        for (auto &x: fi[i])
        {
            long long num = make_query(sg[x].lmax, sg[x].rmax);
            ans[x] -= num;
        }
        for (auto &x: st[i])
        {
            long long num = make_query(sg[x].lmax, sg[x].rmax);
            ans[x] += num;
        }
    }
    for (int i = 0; i <ans.size(); ++ i)
    {
       if(ans[i] > 0)ans[i] = 1;
    }
    return ans;
}

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