Submission #1127953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127953		andrewp	Werewolf (IOI18_werewolf)	C++20	0 / 100	380 ms	67900 KiB

werewolf

//Dedicated to my love,ivaziva 
#include <bits/stdc++.h>   
#include "werewolf.h"
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define sz(a) ((int) (a).size())
#define pb emplace_back 
#define me(a, x) memset(a, x, sizeof(a))   
#define vi vector<int> 
#define i128 __int128  
using namespace std;   
const int maxn = 2e5 + 7;
int n, m, q, inv[maxn], lg[maxn], stMin[maxn][20], stMax[maxn][20];   
vi g[maxn];
vi a;
struct DSU {
    vector<int> p, sz;
    void init(int n) {
        p.resize(n), sz.resize(n);
        L(i, 0, n - 1) {
            p[i] = i;
            sz[i] = 1;
        } 
    }
    int get(int x) {
        return x == p[x] ? x : p[x] = get(p[x]);
    }
    void join(int u, int v) {
        u = get(u), v = get(v);
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        p[v] = u; 
    }
};
void dfs(int x, int par) {
    a.pb(x); 
    for(int u : g[x]) {
        if(u != par) {
            dfs(u, x); 
        }
    }
}
void Build() {
    L(i, 2, n) lg[i] = lg[i >> 1] + 1;
    L(i, 1, n) { 
        stMin[i][0] = a[i - 1]; 
        stMax[i][0] = a[i - 1];  
    }   
    L(j, 1, 19) {
        for(int i = 1; i + (1 << j) <= n + 1; i++) {
            stMin[i][j] = min(stMin[i][j - 1], stMin[i + (1 << (j - 1))][j - 1]);
            stMax[i][j] = max(stMin[i][j - 1], stMin[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int GetMin(int l, int r) {
    l++, r++; 
    int k = lg[r - l + 1];
    return min(stMin[l][k], stMin[r - (1 << k) + 1][k]); 
}
int GetMax(int l, int r) {
    l++, r++;
    int k = lg[r - l + 1];
    return max(stMax[l][k], stMax[r - (1 << k) + 1][k]); 
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L_, vi R_) {
    n = N, m = sz(X), q = sz(S);  
    L(i, 0, m - 1) {
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);  
    }
    vi ans(q, 0);  
    // if(n <= 3000 && m <= 6000 && q <= 3000) { 
    //     DSU dsu; 
    //     L(i, 0, q - 1) {
    //         int s = S[i], e = E[i], l = L_[i], r = R_[i];   
    //         dsu.init(n); 
    //         vi cnt(n, 0); 
    //         L(x, 0, n - 1) { 
    //             for(auto u : g[x]) { 
    //                 if(u >= l && x >= l) {  
    //                     dsu.join(x, u); 
    //                 } 
    //             }
    //         }
    //         L(x, 0, n - 1) {
    //             if(dsu.get(x) == dsu.get(s)) cnt[x]++;  
    //         }   
    //         dsu.init(n);
    //         L(x, 0, n - 1) {
    //             for(auto u : g[x]) {
    //                 if(u <= r && x <= r) {
    //                     dsu.join(x, u); 
    //                 }
    //             }
    //         }
    //         L(x, 0, n - 1) { 
    //             if(dsu.get(x) == dsu.get(e)) cnt[x]++;
    //         }
    //         L(x, 0, n - 1) {
    //             if(cnt[x] >= 2) { 
    //                 ans[i] = 1; 
    //             }
    //         }
    //     }
    // }
    if(m == n - 1) {
        int root = -1;
        L(i, 0, n - 1) {
        	if(sz(g[i]) == 1) {
        		root = i;
        		break;
        	} 
        }
        dfs(root, -1);
        Build();       
        L(i, 0, n - 1) inv[a[i]] = i;
        L(i, 0, q - 1) {
            int s = S[i], e = E[i], l = L_[i], r = R_[i]; 
            int idxS = inv[s], idxE = inv[e];  
            if(idxS < idxE) { 
                int bot = idxS, top = idxE, f = -1, s = -1;
                while(bot <= top) {
                    int mid = bot + top >> 1;
                    if(GetMin(idxS, mid) >= l) {
                        bot = mid + 1;
                        f = mid;
                    } else top = mid - 1;
                } 
                bot = idxS, top = idxE;
                while(bot <= top) {
                    int mid = bot + top >> 1;
                    if(GetMax(mid, idxE) <= r) {
                        top = mid - 1;
                        s = mid;
                    } else bot = mid + 1;
                }
                if(f >= s) ans[i] = 1;
            } else {   
                int bot = idxE, top = idxS, f = idxE, s = idxS;
                while(bot <= top) { 
                    int mid = bot + top >> 1;
                    if(GetMin(mid, idxS) >= l) {
                        top = mid - 1;
                        s = mid;
                    } else bot = mid + 1;
                }     
                bot = idxE, top = idxS; 
                while(bot <= top) {
                    int mid = bot + top >> 1;
                    if(GetMax(idxE, mid) <= r) {
                        bot = mid + 1;
                        f = mid; 
                    } else top = mid - 1;
                }
                if(f >= s) ans[i] = 1;
            }   
        }
    }
    return ans;
}
// int main() { 
//     ios :: sync_with_stdio(false);
//     cin.tie(0); cout.tie(0);
           
//     int N, M, Q; 
//     cin >> N >> M >> Q;
//     vi X(M), Y(M), S(Q), E(Q), L_(Q), R_(Q); 
//     L(i, 0, M - 1) {
//         cin >> X[i] >> Y[i];
//     }
//     L(i, 0, Q - 1) {
//         cin >> S[i] >> E[i] >> L_[i] >> R_[i];
//     }  
//     vi ans = check_validity(N, X, Y, S, E, L_, R_);
//     L(i, 0, Q - 1) {
//         cout << ans[i] << '\n';
//     }
//     cout << '\n'; 
//     return 0;   
// }

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