Submission #772281

#	Time	Username	Problem	Language	Result	Execution time	Memory
772281		I_Love_EliskaM_	Werewolf (IOI18_werewolf)	C++14	100 / 100	1050 ms	202572 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second

struct DSU {
    vector<int> p,sz;
    DSU() {}
    DSU(int n) {
      forn(i,n) p.pb(i), sz.pb(1);
    }
    int get(int u) {
      return p[u]==u?u:get(p[u]);
    }
    void uni(int u, int v) {
      u=get(u), v=get(v);
      if (u==v) return;
      if (sz[u]<sz[v]) swap(u,v);
      p[v]=u;
      sz[u]+=sz[v];
    }
};

const int N=2e5+55;
const int K=20;
struct tree {
    DSU dsu;
    int n,sz;
    vector<vector<int>> adj;
    vector<int> t,p;
    vector<int> ind;
    vector<int> l,r;
    vector<int> ok;
    tree(int _n) {
      n=_n;
      dsu = DSU(n);
      adj.resize(n);
      sz=n;
      forn(i,n) t.pb(i);
      p.assign(n,-1);
      ind.resize(n);
      l.assign(2*n,n-1);
      r.assign(2*n,0);
      ok.assign(2*n,0);
    }
    void add(int u, int v, int x) {
      if (dsu.get(u)==dsu.get(v)) return;
      int U=u, V=v;
      u=t[dsu.get(u)], v=t[dsu.get(v)];
      adj.pb({u,v});
      dsu.uni(U,V);
      t[dsu.get(U)]=sz;
      p[u]=sz;
      p[v]=sz;
      ok[sz]=x;
      p.pb(-1);
      ++sz;
    }
    int z=0;
    void dfs(int u) {
      for(auto&v:adj[u]) {
        dfs(v);
        l[u]=min(l[u],l[v]);
        r[u]=max(r[u],r[v]);
      }
      if (!adj[u].size()) {
        l[u]=r[u]=z;
        ind[u]=z++;
      }
    }
    void dfs() {
      dfs(sz-1);
    }
    vector<vector<int>> go;
    void build() {
      go.assign(sz,vector<int>(K,-1));
      forn(i,sz) go[i][0]=p[i];
      for(int j=1; j<K; ++j) {
        forn(i,sz) {
          if (go[i][j-1]==-1) {
            go[i][j] = -1;
          } else {
            go[i][j] = go[go[i][j-1]][j-1];
          }
        }
      }
      //forn(i,sz) cout<<"! "<<i<<' '<<p[i]<<'\n'; cout<<'\n';
    }
    int get(int u, int x) {
      for (int j=K-1; j>=0; --j) {
        if (go[u][j]==-1) continue;
        if (ok[go[u][j]]>x) continue;
        u=go[u][j];
      }
      return u;
    }
};

struct BIT {
    vector<int> t; int n;
    BIT(int n) {
        this->n=n;
        t.assign(n,0);
    }
    BIT(vector<int> a) {
        n=a.size();
        t.assign(n,0);
        forn(i,n) add(i,a[i]);
    }
    void add(int i, int x) {
        for (; i<n; i=i|(i+1)) t[i]+=x;
    }
    int sum(int r) {
        int q=0;
        for(; r>=0; r=(r&(r+1))-1) q+=t[r];
        return q;
    }
    int sum(int l, int r) {
        if (l>r) return 0;
        return sum(r)-sum(l-1);
    }    
};
vector<int> check_validity(int n, vector<int>x, vector<int>y, vector<int>s, vector<int>e, vector<int>l, vector<int>r) {
    int m=x.size(), q=l.size();    

    vector<vector<int>> adj(n);
    forn(i,m) {
      int u=x[i], v=y[i];
      adj[u].pb(v);
      adj[v].pb(u);
    }

    tree t(n);
    forn(i,n) {
      for(auto&v:adj[i]) if (v<i) t.add(i,v,i);
    }
    t.dfs();
    t.build();
    
    tree t2(n);
    for (int i=n-1; i>=0; --i) {
      for(auto&v:adj[i]) if (v>i) t2.add(t.ind[i],t.ind[v],n-1-i);
    }
    t2.dfs();
    t2.build();

    //forn(i,n) cout<<t.ind[i]<<' '; cout<<'\n';
    //forn(i,n) cout<<t2.ind[i]<<' '; cout<<'\n';
    struct query {
      int l, r, lx, rx;
    };
    vector<query> qry;
    vector<int> res(q,0);
    forn(i,q) {
      int u=e[i], v=s[i], L=l[i], R=r[i];
      u=t.get(u,R);
      v=t2.get(t.ind[v],n-1-L);
      qry.pb({t2.l[v],t2.r[v],t.l[u],t.r[u]}); //t2[l,r], t1[L,R];
      //cout<<"! "<<u<<' '<<t.l[u]<<' '<<t.r[u]<<'\n';
      //cout<<"! "<<v<<' '<<t2.l[v]<<' '<<t2.r[v]<<'\n';
      //cout<<'\n';
    }
    vector<vector<int>> del(n),add(n),ask(n);
    forn(i,q) {
      int lx=qry[i].lx, rx=qry[i].rx;
      if (lx) del[lx-1].pb(i);
      add[rx].pb(i);
    }
    BIT ft(n);
    forn(i,n) {
      ft.add(t2.ind[i],1);
      for(auto&x:del[i]) res[x]-=ft.sum(qry[x].l,qry[x].r);
      for(auto&x:add[i]) res[x]+=ft.sum(qry[x].l,qry[x].r);
    }
    //forn(i,q) cout<<res[i]<<' '; cout<<'\n';
    forn(i,q) res[i]=!!res[i];
    return res;

    return vector<int>(l.size(),0);
}

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