Submission #399456

#	Time	Username	Problem	Language	Result	Execution time	Memory
399456		ljuba	Werewolf (IOI18_werewolf)	C++17	100 / 100	779 ms	131784 KiB

werewolf

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

using namespace std;

const int mxN = 2e5 + 12;
const int mxN2 = 6e5 + 12;

vector<int> adj[mxN];

struct DSU {
    int dsu[mxN2];
    int in[mxN2], out[mxN2];
    vector<int> adj[mxN2];
    vector<int> order;
    int n;
    int timer;

    DSU(int _n) : n(_n) {
        iota(dsu, dsu+mxN2, 0);
        order.push_back(mxN2);
        timer = 0;
    }

    int findSet(int u) {
        if(u == dsu[u])
            return u;
        return dsu[u] = findSet(dsu[u]);
    }

    void unite(int u, int v) {
        u = findSet(u);
        v = findSet(v);
        if(u == v)
            return;
        dsu[u] = dsu[v] = n;
        adj[n].push_back(u);
        adj[n].push_back(v);
        ++n;
    }

    void dfs(int s) {
        order.push_back(s);
        in[s] = ++timer;
        for(auto e : adj[s]) {
            dfs(e);
        }
        out[s] = timer;
    }
};

int ft[mxN2];

void update(int i, int x) {
    for(; i < mxN2; i += i&-i)
        ft[i] += x;
}

int query(int i) {
    int r = 0;
    for(; i; i -= i&-i)
        r += ft[i];
    return 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) {

    int n = N;
    int m = (int)X.size();
    int q = (int)S.size();

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

    vector<int> queryL[mxN];
    vector<int> queryR[mxN];

    for(int i = 0; i < q; ++i) {
        queryL[L[i]].push_back(i);
        queryR[R[i]].push_back(i);
    }

    DSU levi(n);
    for(int i = n-1; ~i; --i) {
        for(auto e : adj[i]) {
            if(e > i)
                levi.unite(i, e);
        }

        for(auto z : queryL[i]) {
            S[z] = levi.findSet(S[z]);
        }
    }

    //for(auto z : S)
        //cerr << z << " ";
    //cerr << endl;
    //cerr << "----------" << endl;

    //cerr << levi.n-1 << " " << levi.findSet(n-1) << endl;
    levi.dfs(levi.n-1);

    DSU desni(n);

    for(int i = 0; i < n; ++i) {
        for(auto e : adj[i]) {
            if(i > e)
                desni.unite(i, e);
        }

        for(auto z : queryR[i]) {
            E[z] = desni.findSet(E[z]);
        }
    }

    //cerr << desni.n-1 << " " << desni.findSet(n-1) << endl;
    desni.dfs(desni.n-1);
    //for(auto z : levi.order)
        //cerr << z << " ";
    //cerr << endl;
    //for(auto z : desni.order)
        //cerr << z << " ";
    //cerr << endl;
    //cerr << "----------" << endl;

    vector<pair<int, int>> doga[mxN2];

    //verovatno ti je ovaj deo los

    for(int i = 0; i < q; ++i) {
        //cerr << levi.in[S[i]] - 1 << " " << levi.out[S[i]] << endl;
        doga[levi.in[S[i]] - 1].push_back({i, -1});
        doga[levi.out[S[i]]].push_back({i, 1});
    }

    //for(int i = 0; i < 50; ++i)
        //cerr << doga[i].size() << " ";
    //cerr << endl;

    vector<int> ans(q);

    //assert((int)levi.order.size() == levi.n);

    for(int i = 0; i < (int)levi.order.size(); ++i) {
        if(levi.order[i] < n)
            update(desni.in[levi.order[i]], 1);
        //cerr << "Vel: " << doga[i].size() << endl;
        for(auto z : doga[i]) {
            int izraz = query(desni.out[E[z.first]]) - query(desni.in[E[z.first]]-1);
            //cerr << "izraz" << endl;
            ans[z.first] += izraz * z.second;
            //cerr << izraz << endl;
        }
    }

    //cerr << "bu" << endl;

    for(auto &z : ans)
        z = (z > 0);

    return ans;
}

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