oj.uz

Submission #477642

# Submission time Handle Problem Language Result Execution time Memory
477642 2021-10-02T23:38:36 Z SirCovidThe19th Werewolf (IOI18_werewolf) C++17
34 / 100
 3155 ms 348772 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 <= b;
        };
        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 Correct 62 ms 98960 KB Output is correct
2 Correct 58 ms 98916 KB Output is correct
3 Runtime error 157 ms 200476 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 98960 KB Output is correct
2 Correct 58 ms 98916 KB Output is correct
3 Runtime error 157 ms 200476 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3155 ms 337668 KB Output is correct
2 Correct 3057 ms 348708 KB Output is correct
3 Correct 2795 ms 347140 KB Output is correct
4 Correct 2544 ms 346292 KB Output is correct
5 Correct 2723 ms 346224 KB Output is correct
6 Correct 2952 ms 346132 KB Output is correct
7 Correct 3082 ms 343772 KB Output is correct
8 Correct 3057 ms 348680 KB Output is correct
9 Correct 2238 ms 345840 KB Output is correct
10 Correct 2428 ms 345000 KB Output is correct
11 Correct 2474 ms 345176 KB Output is correct
12 Correct 2664 ms 345764 KB Output is correct
13 Correct 2479 ms 348744 KB Output is correct
14 Correct 2453 ms 348772 KB Output is correct
15 Correct 2443 ms 348732 KB Output is correct
16 Correct 2416 ms 348744 KB Output is correct
17 Correct 2949 ms 343944 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 98960 KB Output is correct
2 Correct 58 ms 98916 KB Output is correct
3 Runtime error 157 ms 200476 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -