Submission #969779

#	Time	Username	Problem	Language	Result	Execution time	Memory
969779		tnknguyen_	Werewolf (IOI18_werewolf)	C++14	0 / 100	558 ms	236336 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define vi vector<int> 
#define pii pair<int, int>

struct KRT{
    int n, id;
    vector<int> p, eu, in, ou, s, mx;
    vector<vector<int>> gr;

    KRT(int N){
        this->n = N;
        this->id = 1;
        p.assign(2*N + 5, 0);
        s.assign(2*N + 5, 0);
        mx.assign(2*N + 5, 0);
        eu.assign(4*N + 5, 0);
        in.assign(2*N + 5, 0);
        ou.assign(2*N + 5, 0);
        gr.assign(2*N + 5, vector<int>());

        for(int i=1; i<=2*n; ++i){
            mx[i] = p[i] = i;
            s[i] = 1;
        }
    }
    
    int find(int u){
        return (u == p[u] ? u : p[u] = find(p[u]));
    }

    int get(int u){
        return mx[find(u)];
    }

    void add_edge(int u, int v){
        u = find(u), v = find(v);
        if(u == v){
            return;
        }

        ++n;
        gr[n].push_back(mx[u]);
        gr[n].push_back(mx[v]);

        if(s[u] < s[v]){
            swap(u, v);
        }
        s[u] += s[v];
        p[v] = u;
        mx[u] = n;
    }
    
    void dfs(int u){
        in[u] = id;
        int f = 0;
        for(int v : gr[u]){
            dfs(v);
            f = 1;
        }
        if(!f){
            eu[++id] = u;
        }
        ou[u] = id - 1;
    }
};

struct BIT{
    int n;
    vector<int> f;

    BIT(int N){
        this->n = N + 5;
        f.assign(N + 5, 0);
    }

    void update(int i, int val){
        while(i < n){
            f[i] += val;
            i += (i & -i);
        }
    }

    int get(int i){
        int ans = 0;
        while(i > 0){
            ans += f[i];
            i -= (i & -i);
        }
        return ans;
    }

    int get(int l, int r){
        return get(r) - get(l-1);
    }
};

const int MX = 1e6 + 5;
vector<vector<int>> Q[MX];
vector<pii> pf[MX], sf[MX];
vector<pii> wolf[MX], human[MX];
int pf_id[MX], sf_id[MX];
int L[MX], R[MX];
int l1[MX], r1[MX], l2[MX], r2[MX];
int pos[MX], f[MX];

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R){
    int n = N, m = X.size(), q = S.size();
    for(int i=0; i<m; ++i){
        int u = ++X[i], v = ++Y[i];
        pf[max(u, v)].push_back({u, v});
        sf[min(u, v)].push_back({u, v});
    }

    for(int i=0; i<q; ++i){
        int s = ++S[i], e = ++E[i], l = ++L[i], r = ++R[i];
        human[l].push_back({s, i});
        wolf[r].push_back({e, i});
    }

    KRT up(n), dn(n);
    for(int i=1; i<=n; ++i){
        for(pii p : pf[i]){
            int u, v;
            tie(u, v) = p;
            up.add_edge(u, v);
        }
        for(pii p : wolf[i]){
            int u, idx;
            tie(u, idx) = p;
            pf_id[idx] = up.get(u);
        }
    }

    for(int i=n; i>=1; --i){
        for(pii p : sf[i]){
            int u, v;
            tie(u, v) = p;
            dn.add_edge(u, v);
        }
        for(pii p : human[i]){
            int u, idx;
            tie(u, idx) = p;
            sf_id[idx] = dn.get(u);
        }
    }

    up.dfs(up.n);
    dn.dfs(dn.n);

    for(int i=1; i<=up.id; ++i){
        pos[up.eu[i]] = i;
    }

    int idx = 0;
    for(int i=0; i<q; ++i){
        int l = up.in[pf_id[i]], r = up.ou[pf_id[i]], u = dn.in[sf_id[i]], v = dn.ou[sf_id[i]];
        Q[v].push_back({l, r, idx});
        // cout<<v<<' '<<l<<' '<<r<<' '<<idx<<endl;
        L[i] = idx++;
        Q[u - 1].push_back({l, r, idx});
        R[i] = idx;
        // cout<<u-1<<' '<<l<<' '<<r<<' '<<idx<<endl;
        idx++;
    }    

    BIT bit(up.id);
    for(int i=1; i<=up.id; ++i){
        int x = pos[up.eu[i]];
        bit.update(x, 1);

        for(vector<int> v : Q[i]){
            int l = v[0], r = v[1], idx = v[2];
            f[idx] = bit.get(l, r);
        }
    }

    vector<int> ans;
    for(int i=0; i<q; ++i){
        int val = (f[R[i]] - f[L[i]] != 0);
        ans.push_back(val);
    }

    return ans;
}

// int32_t main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);

//     freopen("main.inp","r",stdin);
//     freopen("main.out","w",stdout);

//     // 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});

//     vector<int> ans = 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});

//     for(int x : ans){
//         cout<<x<<endl;
//     }

//     return 0;
// }

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