oj.uz

Submission #850953

# Submission time Handle Problem Language Result Execution time Memory
850953 2023-09-18T02:45:12 Z nonono Werewolf (IOI18_werewolf) C++17
0 / 100
 374 ms 79704 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5 + 10;

struct DSU {
    vector<int> par;
    
    void init(int n) {
        par.resize(n);
        for(int i = 0; i < n; i ++) par[i] = i; 
    }
    
    int get_root(int u) {
        return par[u] == u ? u : par[u] = get_root(par[u]);
    }
};

struct TGraph { 
    int root = 0;
    vector<vector<int>> adj;    
    
    int timer = -1;
    vector<int> in, out;
    int up[mxN][20];
    DSU lnk;
    
    void init(int n) {
        adj.resize(n);    
        in.resize(n);
        out.resize(n);
        lnk.init(n);
    }
    
    void addEdge(int u, int v) {
        u = lnk.get_root(u);
        v = lnk.get_root(v);
        
        if(u == v) return ;
        
        adj[u].push_back(v);
        lnk.par[v] = u;
        root = u;
    }
    
    void dfs(int u) {
        in[u] = ++ timer;
        
        for(int v : adj[u]) {
            up[v][0] = u;
            dfs(v);
        }
        
        out[u] = timer;
    }
    
    void build(int n) {
        up[root][0] = root;
        dfs(root);
        
        for(int k = 1; k <= 18; k ++) {
            for(int u = 0; u <= n - 1; u ++) {
                  up[u][k] = up[up[u][k - 1]][k - 1];
            }
        }
    }
    
    int get(int type, int u, int lim) {
        if(type == 0) for(int k = 18; k >= 0; k --) if(up[u][k] >= lim) u = up[u][k];
        if(type == 1) for(int k = 18; k >= 0; k --) if(up[u][k] <= lim) u = up[u][k];
        return u; 
    }
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, std::vector<int> E,
                                vector<int> L, std::vector<int> R) {
    int Q = S.size();
    int M = X.size();
    
    vector<int> A(Q);
    vector<vector<int>> g(N);
    TGraph tr[2];
    
    for (int i = 0; i < Q; ++i) {
        A[i] = 0;
    }
    
    for(int i = 0; i < M; i ++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    
    tr[0].init(N); 
    tr[1].init(N);
    
    for(int i = N - 1; i >= 0; i --) for(int j : g[i]) if(i < j) tr[0].addEdge(i, j);
    for(int i = 0; i <= N - 1; i ++) for(int j : g[i]) if(i > j) tr[1].addEdge(i, j);
    
    tr[0].build(N); 
    tr[1].build(N);
    
    for(int i = 0; i <= Q - 1; i ++) {
        if(S[i] < E[i]) swap(S[i], E[i]);
        
        int u = tr[0].get(0, S[i], L[i]);
        int v = tr[1].get(1, E[i], R[i]);
        
        if(tr[1].in[v] <= tr[1].in[u] && tr[1].out[u] <= tr[1].out[v]) 
            A[i] = 1;
    }
    
    return A;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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