Submission #526850

#	Time	Username	Problem	Language	Result	Execution time	Memory
526850		qwerasdfzxcl	Werewolf (IOI18_werewolf)	C++14	0 / 100	603 ms	226040 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m, q, num[200200];
vector<int> ans, adj[200200];

struct Query{
    int s, e, l, r, i;
    Query(){}
    Query(int _s, int _e, int _l, int _r, int _i): s(_s), e(_e), l(_l), r(_r), i(_i) {}
    bool operator<(const Query &Q) const{
        return l > Q.l;
    }
};
vector<Query> Q;

struct Range{
    int l, r, t;
    Range(){}
    Range(int _l, int _r, int _t): l(_l), r(_r), t(_t) {}
    bool operator<(const Range &R) const{
        return t < R.t;
    }
};
vector<Range> ran[200200], root[200200];

struct DSU1{
    int path[200200];
    vector<int> S[200200];
    void init(int n){for (int i=0;i<n;i++){path[i] = i; S[i] = {i};}}
    int find(int s){
        if (path[s]==s) return s;
        return find(path[s]);
    }
    void merge(int s, int v, int t){
        s = find(s), v = find(v);
        if (s==v) return;
        if (S[s].size() > S[v].size()) swap(s, v);

        for (auto &x:S[s]){
            num[x] += S[v].size();

            if (!root[x].empty() && root[x].back().t==t) root[x].back().l = v;
            else root[x].emplace_back(v, -1, t);

            S[v].push_back(x);
        }

        path[s] = v;
    }
    void update(int s, int t){
        s = find(s);
        ran[s].emplace_back(S[s][0], S[s].back(), t);
    }
}dsu1;

struct DSU2{
    int path[200200];
    set<int> S[200200];
    void init(int n){for (int i=0;i<n;i++){path[i] = i; S[i].insert(i);}}
    int find(int s){
        if (path[s]==s) return s;
        return find(path[s]);
    }
    void merge(int s, int v){
        s = find(s), v = find(v);
        if (s==v) return;
        if (S[s].size() > S[v].size()) swap(s, v);

        for (auto &x:S[s]) S[v].insert(x);
        path[s] = v;
    }
    bool valid(int s, int l, int r){
        s = find(s);
        auto iter = S[s].lower_bound(l);
        return (iter!=S[s].end() && *iter<=r);
    }
}dsu2;

void init(){ ///renumbering
    dsu1.init(n);
    for (int i=0;i<n;i++){
        root[i].emplace_back(i, -1, -1);
        ran[i].emplace_back(i, i, -1);
    }

    for (int i=0;i<n;i++){
        for (auto &v:adj[i]) if (v<i) dsu1.merge(v, i, i);
        dsu1.update(i, i);
    }

    for (int i=0;i<n;i++){
        for (auto &q:ran[i]) q.l = num[q.l], q.r = num[q.r];
    }
}

pair<int, int> get_range(int s, int t){
    auto iter = upper_bound(root[s].begin(), root[s].end(), Range(-1, -1, t));
    s = prev(iter)->l;

    iter = --upper_bound(ran[s].begin(), ran[s].end(), Range(-1, -1, t));
    return {iter->l, iter->r};
}

std::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) {
    n = N, m = X.size(), q = S.size();
    ans.resize(q);

    for (int i=0;i<m;i++){
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    for (int i=0;i<q;i++) Q.emplace_back(S[i], E[i], L[i], R[i], i);
    sort(Q.begin(), Q.end());

    //printf("YES\n");
    init();
    dsu2.init(n);
    //printf("YES\n");

    int pt = 0;
    for (int i=n-1;i>=0;i--){
        for (auto &v:adj[i]) if (v>i) dsu2.merge(num[v], num[i]);

        for (;pt<q && Q[pt].l==i;pt++){
            auto p = get_range(Q[pt].e, Q[pt].r);
            if (dsu2.valid(Q[pt].s, p.first, p.second)) ans[Q[pt].i] = 1;
        }
    }

    return ans;
}

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