Submission #447551

#	Time	Username	Problem	Language	Result	Execution time	Memory
447551		blue	Werewolf (IOI18_werewolf)	C++17	100 / 100	1398 ms	173164 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxN = 200000;
vector<int> edge[maxN];
vector<int> col(maxN);
vector<int> col_list[maxN];
vector<int> minV(maxN); //min value in color i.
vector<int> child1[maxN];
vector<int> order1;
vector<int> pos1(maxN);
vector<int> subtree1(maxN, 1);
int anc1[maxN][20];
vector<int> depth1(maxN);
void dfs1(int u) {
    // cerr << "dfs1 " << u << '\n';
    pos1[u] = int(order1.size());
    order1.push_back(u);
    for(int v: child1[u]) {
        anc1[v][0] = u;
        for(int e = 1; e < 20; e++)
            anc1[v][e] = anc1[ anc1[v][e-1] ][e-1];
        depth1[v] = depth1[u] + 1;
        dfs1(v);
        subtree1[u] += subtree1[v];
    }
}
vector<int> maxV(maxN);
vector<int> child2[maxN];
vector<int> order2;
vector<int> pos2(maxN);
vector<int> subtree2(maxN, 1);
int anc2[maxN][20];
vector<int> depth2(maxN);
void dfs2(int u) {
    pos2[u] = int(order2.size());
    order2.push_back(u);
    for(int v: child2[u]) {
        anc2[v][0] = u;
        for(int e = 1; e < 20; e++)
            anc2[v][e] = anc2[ anc2[v][e-1] ][e-1];
        depth2[v] = depth2[u] + 1;
        dfs2(v);
        subtree2[u] += subtree2[v];
    }
}
vector<int> init(maxN);
struct segtree {
    int l;
    int r;
    vector<int> V;
    segtree* left = NULL;
    segtree* right = NULL;
    segtree() {
        ;
    }
    segtree(int L, int R) {
        l = L;
        r = R;
        if(l == r) {
            V.push_back(init[l]);
        }
        else {
            int m = (l+r)/2;
            left = new segtree(l, m);
            right = new segtree(m+1, r);
            for(int v: left->V) V.push_back(v);
            for(int v: right->V) V.push_back(v);
            sort(V.begin(), V.end());
        }
    }
    bool query(int L, int R, int X, int Y) {
        if(R < l || r < L) return 0;
        else if(L <= l && r <= R) {
            int s = -1;
            for(int e = 19; e >= 0; e--) {
                if(s + (1 << e) >= V.size()) continue;
                if(V[s + (1 << e)] <= Y)
                    s += (1 << e);
            }
            if(s == -1) return 0;
            return (V[s] >= X);
        }
        else return left->query(L, R, X, Y) || right->query(L, R, X, Y);
    }
};
segtree T;
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();
    for(int j = 0; j < M; j++) {
        edge[X[j]].push_back(Y[j]);
        edge[Y[j]].push_back(X[j]);
    }
    for(int e = 0; e < 20; e++) {
        anc1[0][e] = 0;
        anc2[N-1][e] = N-1;
    }
    depth1[0] = 0;
    depth2[N-1] = 0;
    for(int i = 0; i < N; i++)  {
        col_list[i].push_back(i);
        col[i] = minV[i] = i;
    }
    for(int u = N-1; u >= 0; u--) {
        for(int v: edge[u])  {
            if(v < u) continue;
            if(col[v] == col[u]) continue;
            child1[u].push_back(minV[col[v]]);
            int U = u, V = v;
            if(col_list[col[U]].size() < col_list[col[V]].size())
                swap(U, V);
            int colV = col[V];
            for(int x: col_list[colV])  {
                col[x] = col[U];
                col_list[col[U]].push_back(x);
            }
            minV[col[U]] = u;
        }
    }
    dfs1(0);
    for(int i = 0; i < N; i++) {
        col_list[i].clear();
        col_list[i].push_back(i);
        col[i] = maxV[i] = i;
    }
    for(int u = 0; u < N; u++) {
        for(int v: edge[u]) {
            if(v > u) continue;
            if(col[v] == col[u]) continue;
            child2[u].push_back(maxV[col[v]]);
            int U = u, V = v;
            if(col_list[col[U]].size() < col_list[col[V]].size())
                swap(U, V);
            int colV = col[V];
            for(int x: col_list[colV])  {
                col[x] = col[U];
                col_list[col[U]].push_back(x);
            }
            maxV[col[U]] = u;
        }
    }
    dfs2(N-1);
    for(int i = 0; i < N; i++) 
      init[ pos1[i] ] = pos2[i];
    T = segtree(0, N-1);
    int Q = S.size();
    vector<int> res(Q);
    for(int i = 0; i < Q; i++) {
        int s = S[i], e = E[i], l = L[i], r = R[i];
        for(int x = 19; x >= 0; x--){
            if(anc1[s][x] >= l)
                s = anc1[s][x];
        }
        for(int x = 19; x >= 0; x--) {
            if(anc2[e][x] <= r)
                e = anc2[e][x];
        }
        res[i] = T.query(pos1[s], pos1[s] + subtree1[s] - 1, pos2[e], pos2[e] + subtree2[e] - 1);
    }
    return res;
}

Compilation message (stderr)

werewolf.cpp: In member function 'bool segtree::query(int, int, int, int)':
werewolf.cpp:79:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 if(s + (1 << e) >= V.size()) continue;
      |                    ~~~~~~~~~~~~~^~~~~~~~~~~

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