oj.uz

Submission #1042052

# Submission time Handle Problem Language Result Execution time Memory
1042052 2024-08-02T13:24:12 Z Dan4Life Werewolf (IOI18_werewolf) C++17
100 / 100
 307 ms 110016 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
using ar4 = array<int,4>;
const int mxN = (int)2e5+5;
const int mxLg = 19;
int n,m,q,dfs_timer;
int jmp[2][mxLg][mxN];
vector<ar4> query[mxN];
int st[2][mxN], en[2][mxN], A[2][mxN];
vi adj[mxN], euler[2], adj2[2][mxN];
 
template<int SZ> struct DSU{
    int p[SZ], root;
    void init(int n){ for(int i=0; i<n; i++) p[i]=i;}
    int findSet(int i){return p[i]==i?i:p[i]=findSet(p[i]);}
    bool isSameSet(int i, int j) {return findSet(i)==findSet(j);}
    void unionSet(int t, int i, int j){
        int x = findSet(i), y = findSet(j);
        if(x==y) return;
        adj2[t][x].pb(y); root=x, p[y]=x;
    }
};
DSU<mxN> dsu[2];
 
void dfs(int s, int p, int t){
    st[t][s] = dfs_timer++;
    euler[t].pb(s); jmp[t][0][s] = p;
    for(auto u : adj2[t][s]){
        if(u==p) continue;
        dfs(u,s,t);
    }
    en[t][s] = dfs_timer-1;
}
 
int fen[mxN];
void upd(int x, int v){for (x++;x<mxN;x+=x&-x)fen[x]+=v; }
int sum(int x){ int s=0;for(x++;x>0;x-=x&-x)s+=fen[x]; return s; }

vi check_validity(int _N, vi U, vi V, vi S, vi T, vi L, vi R) {
    n = _N, m = sz(U), q = sz(S);
    vi ans(q,0); memset(jmp,-1,sizeof(jmp));
    dsu[0].init(n), dsu[1].init(n);
    for(int i = 0; i < m; i++){
        int a = U[i], b = V[i];
        adj[a].pb(b), adj[b].pb(a);
    }
    for(int i = n-1; i >= 0; i--)
        for(auto u : adj[i]) if(u>i) 
            dsu[0].unionSet(0,i,u);
    for(int i = 0; i < n; i++)
        for(auto u : adj[i]) if(u<i) 
            dsu[1].unionSet(1,i,u);
    for(int t : {0,1}){
        dfs_timer = 0; dfs(dsu[t].root, -1, t);
        for(int i = 1; i < mxLg; i++)
            for(int j = 0; j < n; j++)
                jmp[t][i][j] = jmp[t][i-1][jmp[t][i-1][j]];
    }
    for(int i = 0; i < q; i++){
        int s = S[i], t = T[i], l = L[i], r = R[i];
        for(int j = mxLg-1; j>=0; j--){
            if(jmp[0][j][s]!=-1 and jmp[0][j][s]>=l) s = jmp[0][j][s];
            if(jmp[1][j][t]!=-1 and jmp[1][j][t]<=r) t = jmp[1][j][t];
        }
        query[en[1][t]].pb({st[0][s],en[0][s],i,1});
        query[st[1][t]-1].pb({st[0][s],en[0][s],i,0});
    }
    for(int j = 0; j < n; j++){
        upd(st[0][euler[1][j]],1);
        for(auto [l,r,i,t] : query[j])
            ans[i]+=(t?1:-1)*(sum(r)-sum(l-1));
    }
    for(auto &u : ans) u=!!u;
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 55900 KB Output is correct
2 Correct 7 ms 55900 KB Output is correct
3 Correct 7 ms 55900 KB Output is correct
4 Correct 6 ms 55644 KB Output is correct
5 Correct 7 ms 55644 KB Output is correct
6 Correct 7 ms 55744 KB Output is correct
7 Correct 6 ms 55644 KB Output is correct
8 Correct 7 ms 55644 KB Output is correct
9 Correct 7 ms 55852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 55900 KB Output is correct
2 Correct 7 ms 55900 KB Output is correct
3 Correct 7 ms 55900 KB Output is correct
4 Correct 6 ms 55644 KB Output is correct
5 Correct 7 ms 55644 KB Output is correct
6 Correct 7 ms 55744 KB Output is correct
7 Correct 6 ms 55644 KB Output is correct
8 Correct 7 ms 55644 KB Output is correct
9 Correct 7 ms 55852 KB Output is correct
10 Correct 9 ms 56412 KB Output is correct
11 Correct 9 ms 56408 KB Output is correct
12 Correct 9 ms 56412 KB Output is correct
13 Correct 9 ms 56568 KB Output is correct
14 Correct 10 ms 56668 KB Output is correct
15 Correct 9 ms 56668 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 96548 KB Output is correct
2 Correct 289 ms 100684 KB Output is correct
3 Correct 260 ms 97864 KB Output is correct
4 Correct 249 ms 96076 KB Output is correct
5 Correct 258 ms 95812 KB Output is correct
6 Correct 266 ms 95800 KB Output is correct
7 Correct 254 ms 95304 KB Output is correct
8 Correct 247 ms 100688 KB Output is correct
9 Correct 217 ms 97600 KB Output is correct
10 Correct 211 ms 95420 KB Output is correct
11 Correct 216 ms 95788 KB Output is correct
12 Correct 210 ms 95712 KB Output is correct
13 Correct 268 ms 105176 KB Output is correct
14 Correct 268 ms 105276 KB Output is correct
15 Correct 273 ms 105276 KB Output is correct
16 Correct 271 ms 105272 KB Output is correct
17 Correct 260 ms 95540 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 55900 KB Output is correct
2 Correct 7 ms 55900 KB Output is correct
3 Correct 7 ms 55900 KB Output is correct
4 Correct 6 ms 55644 KB Output is correct
5 Correct 7 ms 55644 KB Output is correct
6 Correct 7 ms 55744 KB Output is correct
7 Correct 6 ms 55644 KB Output is correct
8 Correct 7 ms 55644 KB Output is correct
9 Correct 7 ms 55852 KB Output is correct
10 Correct 9 ms 56412 KB Output is correct
11 Correct 9 ms 56408 KB Output is correct
12 Correct 9 ms 56412 KB Output is correct
13 Correct 9 ms 56568 KB Output is correct
14 Correct 10 ms 56668 KB Output is correct
15 Correct 9 ms 56668 KB Output is correct
16 Correct 292 ms 96548 KB Output is correct
17 Correct 289 ms 100684 KB Output is correct
18 Correct 260 ms 97864 KB Output is correct
19 Correct 249 ms 96076 KB Output is correct
20 Correct 258 ms 95812 KB Output is correct
21 Correct 266 ms 95800 KB Output is correct
22 Correct 254 ms 95304 KB Output is correct
23 Correct 247 ms 100688 KB Output is correct
24 Correct 217 ms 97600 KB Output is correct
25 Correct 211 ms 95420 KB Output is correct
26 Correct 216 ms 95788 KB Output is correct
27 Correct 210 ms 95712 KB Output is correct
28 Correct 268 ms 105176 KB Output is correct
29 Correct 268 ms 105276 KB Output is correct
30 Correct 273 ms 105276 KB Output is correct
31 Correct 271 ms 105272 KB Output is correct
32 Correct 260 ms 95540 KB Output is correct
33 Correct 295 ms 97080 KB Output is correct
34 Correct 162 ms 89676 KB Output is correct
35 Correct 301 ms 100412 KB Output is correct
36 Correct 291 ms 97364 KB Output is correct
37 Correct 298 ms 99440 KB Output is correct
38 Correct 304 ms 98112 KB Output is correct
39 Correct 296 ms 109384 KB Output is correct
40 Correct 307 ms 105168 KB Output is correct
41 Correct 241 ms 97636 KB Output is correct
42 Correct 199 ms 96072 KB Output is correct
43 Correct 299 ms 105284 KB Output is correct
44 Correct 248 ms 99148 KB Output is correct
45 Correct 246 ms 109384 KB Output is correct
46 Correct 253 ms 110016 KB Output is correct
47 Correct 269 ms 105532 KB Output is correct
48 Correct 294 ms 105372 KB Output is correct
49 Correct 281 ms 100964 KB Output is correct
50 Correct 263 ms 100920 KB Output is correct
51 Correct 266 ms 98920 KB Output is correct
52 Correct 270 ms 98896 KB Output is correct