Submission #1127902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127902		andrewp	Werewolf (IOI18_werewolf)	C++20	0 / 100	115 ms	9912 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;   
int n, m, q;    
vi g[3000]; 
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; 
    }
};
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) { 
        L(i, 0, q - 1) {
            int s = S[i], e = E[i], l = L_[i], r = R_[i];
            DSU dsu; 
            dsu.init(n);
            vi cnt(n, 0); 
            L(x, 0, n - 1) { 
                for(auto u : g[x]) { 
                    if(u >= 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) {
                        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[x] = 1;
                    break;
                }
            }
        }
    } 
    return ans;
}
// int main() { 
//     ios :: sync_with_stdio(false);
//     cin.tie(0); cout.tie(0);
           
//     int N = 6, M = 6, Q = 3; 
//     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];
//     } 
//     L(i, 0, M - 1) {
//         cin >> Y[i];
//     } 
//     L(i, 0, Q - 1) {
//         cin >> S[i];
//     } 
//     L(i, 0, Q - 1) {
//         cin >> E[i];
//     } 
//     L(i, 0, Q - 1) {
//         cin >> L_[i];
//     } 
//     L(i, 0, Q - 1) {
//         cin >> R_[i]; 
//     }
//     vi ans = check_validity(N, X, Y, S, E, L_, R_);
//     L(i, 0, Q - 1) {
//         cout << ans[i] << ' ';
//     }
//     cout << '\n'; 
//     return 0;   
// }

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