Submission #1219487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219487		mactoddlover	Werewolf (IOI18_werewolf)	C++17	100 / 100	509 ms	158664 KiB

werewolf

#include<bits/stdc++.h>

#define fi first
#define se second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)(v).size()
#define vi vector<int>
#define pii pair<int,int>

#define endl "\n"
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;

const int N = 1e6 + 15;

int n, m, q;
int eu[N], ev[N];

struct dsu_tree{
    int n, timerDFS = 0;
    vi lab, tin, tout;
    vector<vi> g;

    dsu_tree(int n) : n(n), lab(n << 1 | 1, -1), g(n << 1 | 1),  tin(n << 1 | 1,0), tout(n << 1 | 1,0) {}

    int asc(int u){
        return lab[u] < 0 ? u : lab[u] = asc(lab[u]);
    }

    void join(int u, int v){
        u = asc(u), v = asc(v);
        if(u == v) return;
        lab[u] = lab[v] = ++n;
        //cout << n << " " << u << endl;
        //cout << n << " " << v << endl;
        g[n].push_back(u), g[n].push_back(v);
    }

    bool inside(int u, int v){
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    }

    void dfs(int u){
        tin[u] = ++timerDFS;
        for(int v : g[u]){
            dfs(v);
        }
        tout[u] = timerDFS;
    }
};

vector<int> queryDown[N], queryUp[N];
int bigU[N], bigV[N];
int bit[N];
vector<int> g[N];

void update(int idx, int v){
    for(;idx <= 2*n; idx += (idx & -idx)) bit[idx] += v;
}

int get(int idx){
    int res = 0;
    for(; idx; idx -= (idx & -idx)){
        assert(idx >= 0);
        res += bit[idx];
    }
    return res;
}

vi check_validity(int _N, vi X, vi Y, vi U, vi V, vi _L, vi _R){
    n = _N;
    m = sz(X);
    q = sz(U);

    for(int i = 1; i <= m; i++){
        tie(eu[i], ev[i]) = {X[i-1], Y[i-1]};
        eu[i]++, ev[i]++;
        g[eu[i]].push_back(ev[i]);
        g[ev[i]].push_back(eu[i]);
    }

    for(int i = 0; i < q; i++){
        _L[i]++, _R[i]++, U[i]++, V[i]++;
        queryDown[_R[i]].emplace_back(i);
        queryUp[_L[i]].emplace_back(i);
    }

    dsu_tree krt1(n), krt2(n);

    for(int i = 1; i <= n; i++){
        for(int v : g[i]){
            if(v > i) continue;
            krt1.join(i, v);
        }
        for(int id : queryDown[i]){
            bigV[id] = krt1.asc(V[id]);
        }
    }

    for(int i = n; i >= 1; i--){
        for(int v : g[i]){
            if(v < i) continue;
            krt2.join(i, v);
        }
        for(int id : queryUp[i]){
            bigU[id] = krt2.asc(U[id]);
        }
    }

    krt1.dfs(2*n - 1);
    krt2.dfs(2*n - 1);

    vector<pii> point;
    vector<pair<pii, int>> query;
    vector<int> ans(q, 0);

    for(int i = 1; i <= n; i++){
        point.emplace_back(krt2.tin[i], krt1.tin[i]);
    }

    for(int i = 0; i < q; i++){
        int x1, x2; tie(x1, x2) = {krt2.tin[bigU[i]], krt2.tout[bigU[i]]};
        int y1, y2; tie(y1, y2) = {krt1.tin[bigV[i]], krt1.tout[bigV[i]]};
        query.push_back({{x2, y2}, +(i+1)});
        if(x1 - 1) query.push_back({{x1 - 1, y2}, -(i+1)});
        if(y1 - 1) query.push_back({{x2, y1 - 1}, -(i+1)});
        if(x1 - 1 && y1 - 1) query.push_back({{x1 - 1, y1 - 1}, +(i+1)});
    }

    sort(all(point));
    sort(all(query), [&](auto a, auto b){
        return a.fi.fi < b.fi.fi;
    });

    for(int i = 0, j = 0; i < sz(query); i++){
        while(j < sz(point) && point[j].fi <= query[i].fi.fi){
            update(point[j].se, 1);
            j++;
        }
        int id = query[i].se;
        int sign = (id < 0) ? -1 : 1;
        id *= sign;
        id--;
        ans[id] += sign*get(query[i].fi.se);
    }

    for(int i = 0; i < sz(ans); i++) if(ans[i]) ans[i] = 1;

    return ans;
}

#ifdef LOCAL
void fastIO(){
    ios_base::sync_with_stdio(NULL); cin.tie(0);
    freopen("task.INP", "r", stdin);
    freopen("task.OUT", "w", stdout);
}

signed main(){
    fastIO();

    vector<int> res = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
}
#endif

//check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
//{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});

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