Submission #164311

#	Time	Username	Problem	Language	Result	Execution time	Memory
164311		qwerty234	Werewolf (IOI18_werewolf)	C++14	100 / 100	1261 ms	141424 KiB

werewolf

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int> 


using namespace std;


const int N = 4e5 + 123;


struct query {
    int La, Ra, Lb, Rb, id;
} qq[N];


struct qwe{
    int k, id, Lb, Rb;
};

vector <qwe> qe[N];
int n, m, q, S[N], E[N], L[N], R[N], Pmin[N], Pmax[N], p[N], sz[N], val[N];
int rootL[N], rootR[N], tinm[N], toutm[N], tin[N], tout[N], timer = 0, tmn[N], tmx[N];
int t[4 * N], to[N], a1[N];
vector <int> Qmin[N], Qmax[N], g[N], gmin[N], gmax[N];


void make_set() {
	for (int i = 0; i < n; i++) {
		sz[i] = 1;
		val[i] = p[i] = i;
	}
}


int getp(int u) {
    if (u == p[u])
        return u;
    p[u] = getp(p[u]);
    return p[u];
}


void un(int u, int v, bool is =0) {
    u = getp(u);
    v = getp(v);
    if (u == v)
        return;
    if (sz[u] > sz[v])
        swap(u, v);
    p[u] = v;
    sz[v] += sz[u];
    if (is)
        val[v] = max(val[v], val[u]);
    else
        val[v] = min(val[v], val[u]);
}


void dfsmax(int u, int p=-1) {
    tinm[u] = ++timer;
    tmx[timer] = u;
    for (int i = 0; i < gmax[u].size(); i++)
        if (gmax[u][i] != p)
            dfsmax(gmax[u][i], u);
    toutm[u] = timer;
}


void dfsmin(int u, int p=-1) {
    tin[u] = ++timer;
    tmn[timer] = u;
    for (int i = 0; i < gmin[u].size(); i++)
        if (gmin[u][i] != p)
            dfsmin(gmin[u][i], u);
    tout[u] = timer;
}


void build(int v, int tl, int tr) {
    t[v] = 0;
    if (tl == tr)
        return;
    int tm = (tl + tr)>>1;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
}


void upd(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        t[v] = 1;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        upd(v * 2, tl, tm, pos);
    else
        upd(v * 2 + 1, tm + 1, tr, pos);
    t[v] = t[v * 2] + t[v * 2 + 1];
}


int get(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l)
        return 0;
    int tm = (tl + tr) / 2;
    if (l <= tl && tr <= r)
        return t[v];
    return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
}


vector<int> check_validity(int n1, vector<int> X, vector<int> Y, vector<int> S1, vector<int> E1, vector<int> L1, vector<int> R1) {
    n = n1;
    m = X.size();
    q = S1.size();
	for (int i = 0; i < q; i++) {
	    S[i] = S1[i];
	    E[i] = E1[i];
	    L[i] = L1[i];
	    R[i] = R1[i];
    }
	for (int i = 0; i < q; i++) {
		Qmin[L[i]].pb(i);
		Qmax[R[i]].pb(i);
	}
	for (int i = 0; i < m; i++) {
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}	
	make_set();
	for (int i = n - 1; i >= 0; i--) {
	    for (int j = 0; j < g[i].size(); j++) {
	        if (getp(i) == getp(g[i][j]) || g[i][j] < i)
	            continue;
	        Pmin[val[getp(g[i][j])]] = i;
	        un(i, g[i][j]);
	    }
	    for (int j = 0; j < Qmin[i].size(); j++) {
	        int v = getp(S[Qmin[i][j]]);
	        rootL[Qmin[i][j]] = val[v];
	    }
	}
	make_set();
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < g[i].size(); j++) {
	        if (getp(i) == getp(g[i][j]) || g[i][j] > i)
	            continue;
	        Pmax[val[getp(g[i][j])]] = i;
	        un(i, g[i][j], 1);
	    }
	    for (int j = 0; j < Qmax[i].size(); j++) {
	        int v = getp(E[Qmax[i][j]]);
	        rootR[Qmax[i][j]] = val[v];
	    }
	}
	Pmax[n - 1] = Pmin[0] = -1;
	for (int i = 0; i < n; i++) {
	    if (i != 0) {
    	    gmin[i].pb(Pmin[i]);
	        gmin[Pmin[i]].pb(i);
	    }
	    if (i != n - 1) {
    	    gmax[i].pb(Pmax[i]);
    	    gmax[Pmax[i]].pb(i);
	    }
	}
	timer = 0;
	dfsmin(0);
	timer = 0;
	dfsmax(n - 1);
	for (int i = 1; i <= n; i++)
	    a1[tmx[i]] = i;
	for (int i = 1; i <= n; i++)
	    to[i] = a1[tmn[i]];
	for (int i = 0; i < q; i++) {
	    qq[i].id = i;
	    qq[i].La = tin[rootL[i]];
	    qq[i].Ra = tout[rootL[i]];
	    qq[i].Lb = tinm[rootR[i]];
	    qq[i].Rb = toutm[rootR[i]];
	    qwe tmp;
	    tmp.Lb = qq[i].Lb;
	    tmp.Rb = qq[i].Rb;
	    tmp.k = 1;
	    tmp.id = i;
	    qe[qq[i].Ra].pb(tmp);
	    tmp.Lb = qq[i].Lb;
	    tmp.Rb = qq[i].Rb;
	    tmp.k = -1;
	    tmp.id = i;
	    qe[qq[i].La - 1].pb(tmp);
	}
    vector <int> ans;
    ans.clear();
    for (int i = 0; i < q; i++)
        ans.pb(0);
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
	    upd(1, 1, n, to[i]);
	    for (int j = 0; j < qe[i].size(); j++) {
	        qwe tmp = qe[i][j];
	        ans[tmp.id] += tmp.k * get(1, 1, n, tmp.Lb, tmp.Rb);
	    }
	}
	for (int i = 0; i < q; i++)
	    if (ans[i] != 0)
	        ans[i] = 1;
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfsmax(int, int)':
werewolf.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < gmax[u].size(); i++)
                     ~~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfsmin(int, int)':
werewolf.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < gmin[u].size(); i++)
                     ~~^~~~~~~~~~~~~~~~
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:138:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int j = 0; j < g[i].size(); j++) {
                      ~~^~~~~~~~~~~~~
werewolf.cpp:144:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int j = 0; j < Qmin[i].size(); j++) {
                      ~~^~~~~~~~~~~~~~~~
werewolf.cpp:151:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int j = 0; j < g[i].size(); j++) {
                      ~~^~~~~~~~~~~~~
werewolf.cpp:157:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int j = 0; j < Qmax[i].size(); j++) {
                      ~~^~~~~~~~~~~~~~~~
werewolf.cpp:201:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < q; i++)
     ^~~
werewolf.cpp:203:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  build(1, 1, n);
  ^~~~~
werewolf.cpp:206:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int j = 0; j < qe[i].size(); j++) {
                      ~~^~~~~~~~~~~~~~

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