oj.uz

Submission #477641

# Submission time Handle Problem Language Result Execution time Memory
477641 2021-10-02T23:29:33 Z SirCovidThe19th Werewolf (IOI18_werewolf) C++17
0 / 100
 3199 ms 346120 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std; 

#define vi vector<int>

const int mx = 6e5 + 5;

struct dsuTree{
    int par[mx], tin[mx], tout[mx], ti, id; vector<int> adj[mx];
    dsuTree(int n){ 
        iota(par, par + n * 2, 0); id = n; 
    }
    int get(int i){ 
        return i == par[i] ? i : par[i] = get(par[i]); 
    }
    void merge(int a, int b){
        a = get(a); b = get(b); if (a == b) return;
        adj[id].push_back(a); adj[id].push_back(b);
        par[a] = par[b] = id++;
    }
    void dfs(int i){
        tin[i] = ti++;
        for (int x : adj[i]) dfs(x);
        tout[i] = ti - 1;
    }
};
struct segTree{
    multiset<int> seg[mx * 2]; 
    void upd(int i, int num){
        for (i += mx; i; i /= 2) seg[i].insert(num);
    }
    bool qry(int l, int r, int a, int b){
        bool ans = 0;
        auto chk = [&](int i){ 
            auto it = seg[i].lower_bound(a);
            return it != seg[i].end() and *it <= r;
        };
        for (l += mx, r += mx; l <= r; r /= 2, l /= 2){
            if (l % 2 == 1) ans |= chk(l++);
            if (r % 2 == 0) ans |= chk(r--);
        }
        return ans;
    }
};
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){
    int m = X.size(), q = L.size(); vi adj[n], QL[n], QR[n];
    
    for (int i = 0; i < m; i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
    for (int i = 0; i < q; i++) QL[L[i]].push_back(i), QR[R[i]].push_back(i);

    dsuTree TL(n), TR(n); vi st1(n), st2(n), ans(q);

    for (int i = n - 1; ~i; i--){
        for (int x : adj[i]) if (x > i){
            TL.merge(i, x); 
        }
        for (int qry : QL[i]) st1[qry] = TL.get(S[qry]);
    }
    for (int i = 0; i < n; i++){
        for (int x : adj[i]) if (x < i) TR.merge(i, x);
        for (int qry : QR[i]) st2[qry] = TR.get(E[qry]);
    }
    TL.dfs(TL.id - 1); TR.dfs(TR.id - 1); segTree seg;

    for (int i = 0; i < n; i++) 
        seg.upd(TL.tin[i], TR.tin[i]);
    for (int i = 0; i < q; i++)
        ans[i] = seg.qry(TL.tin[st1[i]], TL.tout[st1[i]], TR.tin[st2[i]], TR.tout[st2[i]]);
    
    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 99024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 99024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 3199 ms 346120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 99024 KB Output isn't correct
2 Halted 0 ms 0 KB -