Submission #969668

#	Time	Username	Problem	Language	Result	Execution time	Memory
969668		tnknguyen_	Werewolf (IOI18_werewolf)	C++14	0 / 100	116 ms	127404 KiB

werewolf

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

const int MX = 1e6 + 5;
vector<int> gr[4][MX];
int vis[MX];
int n, m, q;
vi X, Y, S, E, L, R;

struct KRT{
    int n;
    vector<int> p;

    KRT(int N){
        this->n = N;
        p.assign(N + 5, 0);
        for(int i=1; i<=n; ++i){
            p[i] = i;
        }    
    }

    int get(int u){
        return (u == p[u] ? u : p[u] = get(p[u]));
    }

    void add(int u, int v, int k){
        u = get(u), v = get(v);
        if(u == v){
            return;
        }
        p[v] = u;
        gr[k][u].push_back(v);
    }
};

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

struct query{
    int l, r, e, s, idx;
};

int in[4][MX], ou[4][MX];
int eu[4][MX];
int id = 0;
void dfs(int u, int p, int k){
    eu[k][++id] = u;
    in[k][u] = id;
    for(int v : gr[k][u]){
        if(v != p){
            dfs(v, u, k);
            eu[k][++id] = u;
            ou[k][u] = id;
        }
    }
}

vector<int> check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){ //returns boolean vector.
    for(int i=0; i<m; ++i){
        int u = X[i], v = Y[i];
        gr[1][u].push_back(v);
        gr[1][v].push_back(u);
    }
    KRT up(n), dn(n);
    for(int i=1; i<=n; ++i){
        for(int u : gr[1][i]){
            if(vis[u] == 1){
                up.add(i, u, 2);
            }
        }
        vis[i] = 1;
    }   
    for(int i=n; i>=1; --i){
        for(int u : gr[1][i]){
            if(vis[u] == 2){
                dn.add(i, u, 3);
            }
        }
        vis[i] = 2;
    }

    for(int i=1; i<=n; ++i){
        if(up.get(i) == i){
            dfs(i, 0, 2);
            break;
        }
    }
    id = 0;
    for(int i=1; i<=n; ++i){
        if(dn.get(i) == i){
            dfs(i, 0, 3);
            break;
        }
    }

    vector<query> Q;
    vector<int> ans;
    for(int i=0; i<q; ++i){
        int s = S[i], e = E[i], l = L[i], r = R[i];
        set<int> se;
        for(int j=in[3][l]+1; j<ou[3][l]; ++j){
            se.insert(eu[3][j]);
        }
        int f = 0;
        for(int j=in[2][r]+1; j<ou[2][r]; ++j){
            if(se.find(eu[2][j]) != se.end()){
                f = 1;
            }
        }
        if(se.find(s) == se.end() || se.find(e) == se.end()){
            f = 0;
        }
        ans.push_back(f);
    }
    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);

//     cin>>n>>m>>q;
//     for(int i=1; i<=m; ++i){
//         int u, v;
//         cin>>u>>v;
//         ++u, ++v;
//         X.push_back(u);
//         Y.push_back(v);
//     }
//     for(int i=1; i<=q; ++i){
//         int s, e, l, r;
//         cin>>s>>e>>l>>r;
//         ++s, ++e, ++l, ++r;
//         S.push_back(s), E.push_back(e), L.push_back(l), R.push_back(r);
//     }

//     vector<int> ans = check_validity(n, X, Y, S, E, L, R);
//     for(int x : ans){
//         cout<<x<<' ';
//     }

//     return 0;
// }

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