oj.uz

Submission #806589

# Submission time Handle Problem Language Result Execution time Memory
806589 2023-08-04T08:10:44 Z Trisanu_Das Werewolf (IOI18_werewolf) C++17
100 / 100
 629 ms 158876 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{
        if (nodes[a].size() > nodes[b].size()) swap(a, b); 
        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 23 ms 42580 KB Output is correct
2 Correct 23 ms 42592 KB Output is correct
3 Correct 23 ms 42580 KB Output is correct
4 Correct 20 ms 42568 KB Output is correct
5 Correct 22 ms 42580 KB Output is correct
6 Correct 21 ms 42580 KB Output is correct
7 Correct 22 ms 42580 KB Output is correct
8 Correct 22 ms 42580 KB Output is correct
9 Correct 22 ms 42552 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42580 KB Output is correct
2 Correct 23 ms 42592 KB Output is correct
3 Correct 23 ms 42580 KB Output is correct
4 Correct 20 ms 42568 KB Output is correct
5 Correct 22 ms 42580 KB Output is correct
6 Correct 21 ms 42580 KB Output is correct
7 Correct 22 ms 42580 KB Output is correct
8 Correct 22 ms 42580 KB Output is correct
9 Correct 22 ms 42552 KB Output is correct
10 Correct 29 ms 43864 KB Output is correct
11 Correct 24 ms 43868 KB Output is correct
12 Correct 24 ms 44032 KB Output is correct
13 Correct 24 ms 43752 KB Output is correct
14 Correct 25 ms 43728 KB Output is correct
15 Correct 27 ms 43912 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 158876 KB Output is correct
2 Correct 400 ms 117172 KB Output is correct
3 Correct 430 ms 121860 KB Output is correct
4 Correct 442 ms 130084 KB Output is correct
5 Correct 452 ms 131660 KB Output is correct
6 Correct 504 ms 137812 KB Output is correct
7 Correct 498 ms 158148 KB Output is correct
8 Correct 409 ms 117208 KB Output is correct
9 Correct 372 ms 120652 KB Output is correct
10 Correct 355 ms 128684 KB Output is correct
11 Correct 376 ms 130280 KB Output is correct
12 Correct 465 ms 138408 KB Output is correct
13 Correct 373 ms 119104 KB Output is correct
14 Correct 370 ms 119148 KB Output is correct
15 Correct 417 ms 119084 KB Output is correct
16 Correct 455 ms 119088 KB Output is correct
17 Correct 580 ms 157496 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42580 KB Output is correct
2 Correct 23 ms 42592 KB Output is correct
3 Correct 23 ms 42580 KB Output is correct
4 Correct 20 ms 42568 KB Output is correct
5 Correct 22 ms 42580 KB Output is correct
6 Correct 21 ms 42580 KB Output is correct
7 Correct 22 ms 42580 KB Output is correct
8 Correct 22 ms 42580 KB Output is correct
9 Correct 22 ms 42552 KB Output is correct
10 Correct 29 ms 43864 KB Output is correct
11 Correct 24 ms 43868 KB Output is correct
12 Correct 24 ms 44032 KB Output is correct
13 Correct 24 ms 43752 KB Output is correct
14 Correct 25 ms 43728 KB Output is correct
15 Correct 27 ms 43912 KB Output is correct
16 Correct 548 ms 158876 KB Output is correct
17 Correct 400 ms 117172 KB Output is correct
18 Correct 430 ms 121860 KB Output is correct
19 Correct 442 ms 130084 KB Output is correct
20 Correct 452 ms 131660 KB Output is correct
21 Correct 504 ms 137812 KB Output is correct
22 Correct 498 ms 158148 KB Output is correct
23 Correct 409 ms 117208 KB Output is correct
24 Correct 372 ms 120652 KB Output is correct
25 Correct 355 ms 128684 KB Output is correct
26 Correct 376 ms 130280 KB Output is correct
27 Correct 465 ms 138408 KB Output is correct
28 Correct 373 ms 119104 KB Output is correct
29 Correct 370 ms 119148 KB Output is correct
30 Correct 417 ms 119084 KB Output is correct
31 Correct 455 ms 119088 KB Output is correct
32 Correct 580 ms 157496 KB Output is correct
33 Correct 599 ms 134696 KB Output is correct
34 Correct 208 ms 76608 KB Output is correct
35 Correct 629 ms 129460 KB Output is correct
36 Correct 612 ms 138588 KB Output is correct
37 Correct 575 ms 129744 KB Output is correct
38 Correct 550 ms 135420 KB Output is correct
39 Correct 453 ms 118584 KB Output is correct
40 Correct 461 ms 134868 KB Output is correct
41 Correct 487 ms 130492 KB Output is correct
42 Correct 479 ms 136864 KB Output is correct
43 Correct 588 ms 131388 KB Output is correct
44 Correct 486 ms 130120 KB Output is correct
45 Correct 427 ms 118344 KB Output is correct
46 Correct 451 ms 117524 KB Output is correct
47 Correct 398 ms 126228 KB Output is correct
48 Correct 361 ms 126108 KB Output is correct
49 Correct 398 ms 126280 KB Output is correct
50 Correct 418 ms 126068 KB Output is correct
51 Correct 450 ms 133156 KB Output is correct
52 Correct 483 ms 133200 KB Output is correct