Submission #476679

#	Time	Username	Problem	Language	Result	Execution time	Memory
476679		cookiemonster04	Werewolf (IOI18_werewolf)	C++17	100 / 100	1128 ms	129536 KiB

werewolf

#include<bits/stdc++.h>
#include<unordered_set>

using namespace std;
#define LL long long
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define f first
#define s second

vector<vector<int>> adj;

struct DSU {
	vector<int> par, size, top;
    bool topmax;
	DSU(int N, bool mx){
		par.resize(N); size.resize(N); top.resize(N);
	    for (int i = 0; i < N; ++i) {
            size[i] = 1;
	        par[i] = i;
            top[i] = i;
	    }
        topmax = mx;
	}
	int find(int node) {
	    if (par[node] != node) {
	    	par[node] = find(par[node]);
	    }
	    return par[node];
	}
	void merge(int A, int B) {
	    int rootA = find(A);
	    int rootB = find(B);
		if (rootA == rootB) return;
        top[rootA] = top[rootB] = topmax ? max(top[rootA], top[rootB]) : min(top[rootA], top[rootB]);
	    if (size[rootA] > size[rootB]) {
	        par[rootB] = rootA;
	        size[rootA] += size[rootB];
	    }
	    else {
	        par[rootA] = rootB;
	        size[rootB] += size[rootA];
	    }
	}
};

struct MST {
    vector<vector<int>> tree;
    vector<int> lBound, rBound;
    MST(vector<int> &input) {
        tree.resize(4*input.size()+1);
        lBound.resize(4*input.size()+1);
        rBound.resize(4*input.size()+1);
        build(0, 0, input.size()-1, input);
    }
    void build(int node, int L, int R, vector<int> &arr) {
        lBound[node] = L; rBound[node] = R;
        if (L == R) {
            tree[node].pb(arr[L]); return;
        }
        build(2*node+1, L, (L+R)/2, arr); build(2*node+2, (L+R)/2+1, R, arr);
        auto lptr = tree[2*node+1].begin(), rptr = tree[2*node+2].begin();
        auto lend = tree[2*node+1].end(), rend = tree[2*node+2].end();
        while(lptr != lend && rptr != rend) {
            if (*lptr < *rptr) {
                tree[node].pb(*lptr);
                lptr++;
            } else {
                tree[node].pb(*rptr);
                rptr++;
            }
        }
        while(lptr != lend) {
            tree[node].pb(*lptr);
            lptr++;
        }
        while(rptr != rend) {
            tree[node].pb(*rptr);
            rptr++;
        }
    }
    bool contains(int node, int dL, int dR) {
        if (tree[node].back() < dL || tree[node].front() > dR) return false;
        int min = -1, max = tree[node].size()-1;
        while(max-min > 1) {
            int mid = (min+max) >> 1;
            if (tree[node][mid] >= dL) {
                max = mid;
            } else {
                min = mid;
            }
        }
        if (tree[node][max] <= dR) return true;
        return false;
    }
    bool query(int node, int qL, int qR, int dL, int dR) {
        if (qR < lBound[node] || qL > rBound[node]) return false;
        if (qL <= lBound[node] && rBound[node] <= qR) {
            return contains(node, dL, dR);
        }
        return query(2*node+1, qL, qR, dL, dR) || query(2*node+2, qL, qR, dL, dR);
    }
};


vector<int> hstart, hend, wstart, wend;

int hpar[19][200005], wpar[19][200005];

vector<int> input;

void hdfs(int c, int p, vector<int> &heuler, vector<vector<int>> &hadj) {
    hpar[0][c] = p;
    hstart[c] = heuler.size();
    heuler.pb(c);
    for (int to : hadj[c]) {
        hdfs(to, c, heuler, hadj);
    }
    hend[c] = heuler.size()-1;
}

int cwidx = 0;
void wdfs(int c, int p, vector<int> &widx, vector<vector<int>> &wadj) {
    wpar[0][c] = p;
    widx[c] = cwidx;
    wstart[c] = cwidx;
    cwidx++;
    for (int to : wadj[c]) {
        wdfs(to, c, widx, wadj);
    }
    wend[c] = cwidx-1;
}

void input_gen(int N, vector<int> &X, vector<int> &Y, vector<int> &S, vector<int> &E, vector<int> &L, vector<int> &R) {
    vector<int> heuler, widx;
    vector<vector<int>> hadj, wadj;
    adj.resize(N+5);
    for (int i = 0; i < X.size(); i++) {
        adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]);
    }
    hadj.resize(N+5); wadj.resize(N+5);
    widx.resize(N+5);
    DSU h(N+5, false), w(N+5, true);

    for (int i = N-1; i >= 0; i--) {
        unordered_set<int> added;
        for (int to : adj[i]) {
            if (to > i) {
                int root = h.find(to);
                int rtop = h.top[root];
                if (added.find(rtop) == added.end()) {
                    added.insert(rtop);
                    hadj[i].pb(rtop);
                }
            }
        }
        for (int val : added) h.merge(i, val);
    }
    for (int i = 0; i < N; i++) {
        unordered_set<int> added;
        for (int to : adj[i]) {
            if (to < i) {
                int root = w.find(to);
                int rtop = w.top[root];
                if (added.find(rtop) == added.end()) {
                    added.insert(rtop);
                    wadj[i].pb(rtop);
                }
            }
        }
        for (int val : added) w.merge(i, val);
    }

    hdfs(0, -1, heuler, hadj); wdfs(N-1, -1, widx, wadj);

    input.resize(N);
    for (int i = 0; i < N; i++) {
        input[i] = widx[heuler[i]];
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    ios::sync_with_stdio(0);
    hstart.resize(N+5); hend.resize(N+5);
    wstart.resize(N+5); wend.resize(N+5);

    input_gen(N, X, Y, S, E, L, R);

    MST tree(input);

    for (int i = 1; i <= 18; i++) {
        for (int j = 0; j < N; j++) {
            if (hpar[i-1][j] == -1) hpar[i][j] = -1;
            else hpar[i][j] = hpar[i-1][hpar[i-1][j]];
            if (wpar[i-1][j] == -1) wpar[i][j] = -1;
            else wpar[i][j] = wpar[i-1][wpar[i-1][j]];
        }
    }
    vector<int> ret;
    for (int q = 0; q < S.size(); q++) {
        if (S[q] < L[q] || E[q] > R[q]) {
            cout << 0 << endl; continue;
        }
        for (int i = 18; i >= 0; i--) {
            if (hpar[i][S[q]] >= L[q]) {
                S[q] = hpar[i][S[q]];
            }
            if (wpar[i][E[q]] != -1 && wpar[i][E[q]] <= R[q]) {
                E[q] = wpar[i][E[q]];
            }
        }
        ret.pb(tree.query(0, hstart[S[q]], hend[S[q]], wstart[E[q]], wend[E[q]]));
    }
    return ret;
}

// int main() {
//     int N, M, Q;
//     cin >> N >> M >> Q;
//     vector<int> X, Y, S, E, L, R;
//     for (int i = 0; i < M; i++) {
//         int a, b;
//         cin >> a >> b;
//         X.pb(a); Y.pb(b);
//     }
//     for (int i = 0; i < Q; i++) {
//         int s, e, l, r;
//         cin >> s >> e >> l >> r;
//         S.pb(s); E.pb(e); L.pb(l); R.pb(r);
//     }
//     vector<int> ret = check_validity(N, X, Y, S, E, L, R);
//     for (int i = 0; i < ret.size(); i++) {
//         cout << ret[i] << endl;
//     }
// }

Compilation message (stderr)

werewolf.cpp: In function 'void input_gen(int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
werewolf.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 0; i < X.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:201:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for (int q = 0; q < S.size(); q++) {
      |                     ~~^~~~~~~~~~

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