Submission #985759

#	Time	Username	Problem	Language	Result	Execution time	Memory
985759		jay_jayjay	Werewolf (IOI18_werewolf)	C++17	100 / 100	713 ms	171828 KiB

werewolf

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
#include "werewolf.h"

struct query {
        int id, s, t, l, r;
};
struct event {
        int id, ty, t, l, r;
        bool operator<(const event& o) const {
                return make_pair(t, ty) < make_pair(o.t, o.ty);
        }
};

struct fenwick {
        int n;vector<int> t;
        fenwick(int n):n(n),t(n,0){};
        void add(int i, int x) {
                for(;i<n;i|=i+1)t[i]+=x;
        }
        int query(int i) {
                int x=0;for(;~i;i=(i&(i+1))-1)x+=t[i];
                return x;
        }
};

int n,q;
vector<vector<int>> adj;
vector<int> ans;
vector<query> qs;
fenwick ft(0);

struct kruskal_tree {
        int m,rt;
        vector<int> up;
        vector<vector<int>> ch;
        vector<int> tin, tout;
        vector<vector<int>> bl;
        int ti=0;

        kruskal_tree() : m(2*n), up(m,-1), ch(m), tin(m), tout(m), bl(20, vector<int>(m)) {}

        int find(int x) { return up[x]<0?x:up[x]=find(up[x]); }

        void dfs(int v) {
                tin[v]=ti;
                if(v>=n)ti++;
                for(auto x:ch[v])dfs(x);
                tout[v]=ti-1;
        }

        void build(bool rev) {
                if(!rev) {
                        for(int i=0;i<n;i++) {
                                bl[0][i+n] = up[i+n] = i;
                                ch[i].push_back(i+n);
                                for(auto j:adj[i]) {
                                        //for(int i=0;i<m;i++)printf("%d ",up[i]);printf("\n");
                                        int u = find(i+n);
                                        int v = find(j+n);
                                        if(j<i && v!=u) {
                                                //printf("U %d <- %d\n", i, j);
                                                //printf("par %d = %d\n", v, i);
                                                ch[i].push_back(v);
                                                bl[0][v]=up[v]=i;
                                        }
                                }
                        }
                        rt=bl[0][n-1]=n-1;
                }
                else {
                        for(int i=n-1;~i;i--) {
                                bl[0][i+n] = up[i+n] = i;
                                ch[i].push_back(i+n);
                                for(auto j:adj[i]) {
                                        int u = find(i+n);
                                        int v = find(j+n);
                                        if(j>i && v!=u) {
                                                //printf("U %d <- %d\n", i, j);
                                                //printf("par %d = %d\n", v, i);
                                                ch[i].push_back(v);
                                                bl[0][v]=up[v]=i;
                                        }
                                }
                        }
                        rt=bl[0][0]=0;
                }
                for(int l=1;l<20;l++)
                        for(int i=0;i<m;i++)
                                bl[l][i]=bl[l-1][bl[l-1][i]];
                dfs(rt);

                //for(int i=0;i<m;i++)printf("%d ",bl[0][i]);
                //printf("\n");
        }

        int jump(int v, int x) {
                bool rev = rt==0;
                //printf("jump %d %d (%d) = ",v,x,rev);
                if(!rev) {
                        for(int l=19;~l;l--)
                                if(bl[l][v]<=x)v=bl[l][v];
                }
                else {
                        for(int l=19;~l;l--)
                                if(bl[l][v]>=x)v=bl[l][v];
                }
                //printf("%d\n",v);
                return v;
        }
};

void solve() {
        kruskal_tree hkt, wkt;
        wkt.build(0);
        hkt.build(1);

        vector<event> evs;
        for(int i=0;i<n;i++) {
                evs.push_back({-1, 2, wkt.tin[i+n], hkt.tin[i+n], -1});
                //printf("%d %d\n", wkt.tin[i+n], hkt.tin[i+n]);
        }

        for(auto [id, s,t,l,r] : qs) {
                int vw = wkt.jump(t+n, r);
                int vh = hkt.jump(s+n, l);
                evs.push_back({id, 1, wkt.tin[vw], hkt.tin[vh], hkt.tout[vh]});
                evs.push_back({id, 3, wkt.tout[vw], hkt.tin[vh], hkt.tout[vh]});
                //printf("%d %d | %d %d\n", wkt.tin[vw], wkt.tout[vw], hkt.tin[vh], hkt.tout[vh]);
        }

        sort(all(evs));
        for(auto [id, ty, t, l, r] : evs) {
                //printf("event %d \t%d %d \t| %d %d\n", id, ty, t, l, r);
                if(ty==2) ft.add(l, 1);
                if(ty==3) ans[id] += ft.query(r)-ft.query(l-1);
                if(ty==1) ans[id] -= ft.query(r)-ft.query(l-1);
        }
        for(auto&x:ans)x=!!x;
}

vector<int> check_validity(int N, vector<int> e1, vector<int> e2,
                vector<int> st, vector<int> en,
                vector<int> ls, vector<int> rs) {
        n=N;
        ft=fenwick(n);
        adj.resize(n);
        q=st.size();
        for(int i=0;i<e1.size();i++)
                adj[e1[i]].push_back(e2[i]),
                adj[e2[i]].push_back(e1[i]);
        ans.resize(q);qs.resize(q);
        for(int i=0;i<q;i++) qs[i]={i,st[i],en[i],ls[i],rs[i]};

        solve();

        return ans;
}

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

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