Submission #1196041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196041		tkm_algorithms	Werewolf (IOI18_werewolf)	C++20	100 / 100	491 ms	120848 KiB

werewolf

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int ll

const char nl = '\n';

const int N = 2e5+5;
vector<int> g[N], taze1[N], taze2[N];
vector<pair<int, int>> qqq[N], otv[N];
int par1[N][21], par2[N][21];
int tin1[N], tout1[N];
int tin2[N], tout2[N];

class DisjointSets {
  private:
    vector<int> parents;
    vector<int> sizes;

  public:
    DisjointSets(int size) : parents(size), sizes(size, 1) {
        for (int i = 0; i < size; i++) { parents[i] = i; }
    }

    /** @return the "representative" node in x's component */
    int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

    /** @return whether the merge changed connectivity */
    bool unite(int x, int y) {
        int x_root = find(x);
        int y_root = find(y);
        if (x_root == y_root) { return false; }

        parents[y_root] = x_root;
        return true;
    }

    /** @return whether x and y are in the same connected component */
    bool connected(int x, int y) { return find(x) == find(y); }
};

int t1, t2;
int id1[N], id2[N];
int vis[N], vis2[N];

void dfs1(int u) {
    id1[t1] = u, vis[u] = 1;
    tin1[u] = tout1[u] = t1++;
    for (auto i: taze1[u]) {
        if (vis[i] == 1)continue;
        //assert(vis[i] == 0)
        dfs1(i);
        tout1[u] = max(tout1[u], tout1[i]);
    }
}

void dfs2(int u) {
    id2[t2] = u;
    vis2[u] = 1;
    tin2[u] = tout2[u] = t2++;
    for (auto i: taze2[u]) {
        if (vis2[i] == 1)continue;
        dfs2(i);
        tout2[u] = max(tout2[u], tout2[i]);
    }
}

void b1(int u, int p) {
    par1[u][0] = p;
    for (int i = 1; i <= 20; ++i) {
		if (par1[u][i-1] == -1)break;
		par1[u][i] = par1[par1[u][i-1]][i-1];
	}
	
	for (auto i: taze1[u])
		b1(i, u);
}

void b2(int u, int p) {
	par2[u][0] = p;
    for (int i = 1; i <= 20; ++i) {
		if (par2[u][i-1] == -1)break;
		par2[u][i] = par2[par2[u][i-1]][i-1];
	}
	
	for (auto i: taze2[u])
		b2(i, u);
}

int calc(int s, int t, int l, int r) {
    //return 0;
    
    
    //cout << pa << " " << t << nl;
    //cout << tin1[s] << " " << tout1[s] << nl;
    for (int i = tin1[s]; i <= tout1[s]; ++i) {
        int x = id1[i];
        if (tin2[x] >= tin2[t] && tout2[x] <= tout2[t])return 1;
    }
    
    return 0;
}

int fnd1(int u, int x) {
	for (int i = 20; i >= 0; --i) {
		if (par1[u][i] == -1)continue;
		if (par1[u][i] >= x)u = par1[u][i];
	}
	
	return u;
}

int fnd2(int u, int x) {
	for (int i = 20; i >= 0; --i) {
		if (par2[u][i] == -1)continue;
		if (par2[u][i] <= x)u = par2[u][i];
	}
	
	return u;
}

struct segtree {
    vector<int> tree;
    int size;
    
    void init(int n) {
        size = 1;
        while (size < n)size <<= 1;
        tree.assign(2*size-1, 0);
    }
    
    void add(int i, int x, int lx, int rx) {
        if (rx-lx==1) {
            tree[x]+=1;
            return;
        }
        
        int mid = lx+rx>>1;
        if (i < mid)add(i, 2*x+1, lx, mid);
        else add(i, 2*x+2, mid, rx);
        tree[x] = tree[2*x+1]+tree[2*x+2];
    }
    
    void add(int i) {
        add(i, 0, 0, size);
    }
    
    int get(int l, int r, int x, int lx, int rx) {
        if (rx <= l || r <= lx)return 0;
        if (lx >= l && rx <= r)return tree[x];
        int mid = (lx + rx) >> 1;
        return get(l, r, 2*x+1, lx, mid)+get(l, r, 2*x+2, mid, rx);
    }
    
    int get(int l, int r) {
        return get(l, r, 0, 0, size);
    }
};

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) {
  int q = s.size(), m = sz(x);
  for (int i = 0; i < m; ++i) {
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }
  
  DisjointSets human(n);
    
    // for (int i = 0; i < n; ++i)
    //     par1[i] = par2[i] = -1;
    
    vector<int> mark1(n+1);
    for (int i = n-1; i >= 0; --i) {
        mark1[i] = 1;
        for (auto j: g[i]) { // small to large
            if (mark1[j]) {
                int c = human.find(j);
                if (human.unite(i, c)) {
                    taze1[i].push_back(c);
                    // par1[c] = i;
                }
            }
        }
    }
    
    DisjointSets wolf(n+1);
    vector<int> mark2(n+1);
    for (int i = 0; i < n; ++i) {
        mark2[i] = 1;
        for (auto j: g[i]) { // large to small
            if (mark2[j]) {
                int c = wolf.find(j);
                if (wolf.unite(i, c)) {
                    taze2[i].push_back(c);
                    // par2[c] = i;
                }
            }
        }
    }
    
    memset(par1, -1, sizeof par1);
    memset(par2, -1, sizeof par2);
    
    dfs1(0);
    dfs2(n-1);
    b1(0, -1);
    b2(n-1, -1);
    
    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        
        s[i] = fnd1(s[i], l[i]);
        e[i] = fnd2(e[i], r[i]);
        //while (par1[s[i]][0] != -1 && par1[s[i]][0] >= l[i]) {
			//s[i] = par1[s[i]][0];
		//}
	
		//while (par2[e[i]][0] != -1 && par2[e[i]][0] <= r[i]) {
			//e[i] = par2[e[i]][0];
		//}
        
        if (tin1[s[i]] > 0) {
            qqq[tin1[s[i]]-1].push_back({tin2[e[i]], tout2[e[i]]});
            otv[tin1[s[i]]-1].push_back({i, -1});
        }
        
        qqq[tout1[s[i]]].push_back({tin2[e[i]], tout2[e[i]]});
        otv[tout1[s[i]]].push_back({i, 1});
    }
    
    segtree st;
    st.init(n+1);
    
    for (int i = 0; i < n; ++i) {
        st.add(tin2[id1[i]]);
        for (int j = 0; j < sz(qqq[i]); ++j) {
            auto &qu = qqq[i][j];
            auto &aa = otv[i][j];
            int sum = st.get(qu.first, qu.second+1);
            ans[aa.first] += sum*aa.second;
        }
    }
    
    for (auto &i: ans)
        if (i > 0)i = 1;
    
    return ans;
}


//void solve() {
    //int n, m, q; cin >> n >> m >> q;
    //vector<int> x(m), y(m);
    //for (int i = 0; i < m; ++i)cin >> x[i] >> y[i];
    
    //vector<int> s(q), e(q), l(q), r(q);
    //for (int i = 0; i < q; ++i)cin >> s[i] >> e[i] >> l[i] >> r[i];
    
    
    //vector<int> ans = check_validity(n, x, y, s, e, l, r);
    //for (auto i: ans)cout << i << nl;
//}

//int32_t main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //int t = 1;
    //for (int _ = 0; _ < t; ++_) {
        //solve();
    //}
    //return 0;
//}

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