oj.uz

Submission #477657

# Submission time Handle Problem Language Result Execution time Memory
477657 2021-10-03T01:41:32 Z SirCovidThe19th Werewolf (IOI18_werewolf) C++17
15 / 100
 1466 ms 524292 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std; 

#define vi vector<int>

const int mx = 6e5 + 5;

int par[mx], tin[mx], tout[mx], ti, id; vector<int> dsuAdj[mx]; set<int> nodes[mx];

int get(int i){ 
    return i == par[i] ? i : par[i] = get(par[i]); 
}
void merge(int a, int b, bool build){
    a = get(a); b = get(b); if (a == b) return;
    if (build){
        dsuAdj[id].push_back(a); dsuAdj[id].push_back(b);
        par[a] = par[b] = id++;
    }
    else{
        par[a] = b;
        nodes[b].insert(nodes[a].begin(), nodes[a].end());
    }
}
void dfs(int i){
    tin[i] = ti++;
    for (int x : dsuAdj[i]) dfs(x);
    tout[i] = ti - 1;
}

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], st(q), ans(q);
    
    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);

    iota(par, par + n * 2, 0); id = n;
    for (int i = n - 1; ~i; i--){
        for (int x : adj[i]) if (x > i) merge(i, x, 1); 
        for (int qry : QL[i]) st[qry] = get(S[qry]);
    }
    
    dfs(id - 1); 
    for (int i = 0; i < n; i++) nodes[i].insert(tin[i]);
    
    iota(par, par + n * 2, 0);
    for (int i = 0; i < n; i++){
        for (int x : adj[i]) if (x < i) merge(i, x, 0);
        for (int qry : QR[i]){
            int cmp = get(E[qry]);
            auto it = nodes[cmp].lower_bound(tin[st[qry]]);
            if (it != nodes[cmp].end() and *it <= tout[st[qry]]) ans[qry] = 1;
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42572 KB Output is correct
2 Correct 23 ms 42540 KB Output is correct
3 Correct 21 ms 42604 KB Output is correct
4 Correct 25 ms 42572 KB Output is correct
5 Correct 22 ms 42576 KB Output is correct
6 Correct 25 ms 42560 KB Output is correct
7 Correct 23 ms 42600 KB Output is correct
8 Correct 22 ms 42632 KB Output is correct
9 Correct 25 ms 42572 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42572 KB Output is correct
2 Correct 23 ms 42540 KB Output is correct
3 Correct 21 ms 42604 KB Output is correct
4 Correct 25 ms 42572 KB Output is correct
5 Correct 22 ms 42576 KB Output is correct
6 Correct 25 ms 42560 KB Output is correct
7 Correct 23 ms 42600 KB Output is correct
8 Correct 22 ms 42632 KB Output is correct
9 Correct 25 ms 42572 KB Output is correct
10 Correct 118 ms 75324 KB Output is correct
11 Correct 89 ms 63816 KB Output is correct
12 Correct 30 ms 44356 KB Output is correct
13 Correct 29 ms 43556 KB Output is correct
14 Correct 29 ms 43608 KB Output is correct
15 Correct 45 ms 49368 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 210244 KB Output is correct
2 Runtime error 1466 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 42572 KB Output is correct
2 Correct 23 ms 42540 KB Output is correct
3 Correct 21 ms 42604 KB Output is correct
4 Correct 25 ms 42572 KB Output is correct
5 Correct 22 ms 42576 KB Output is correct
6 Correct 25 ms 42560 KB Output is correct
7 Correct 23 ms 42600 KB Output is correct
8 Correct 22 ms 42632 KB Output is correct
9 Correct 25 ms 42572 KB Output is correct
10 Correct 118 ms 75324 KB Output is correct
11 Correct 89 ms 63816 KB Output is correct
12 Correct 30 ms 44356 KB Output is correct
13 Correct 29 ms 43556 KB Output is correct
14 Correct 29 ms 43608 KB Output is correct
15 Correct 45 ms 49368 KB Output is correct
16 Correct 978 ms 210244 KB Output is correct
17 Runtime error 1466 ms 524292 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -