oj.uz

Submission #401036

# Submission time Handle Problem Language Result Execution time Memory
401036 2021-05-09T08:37:10 Z Jarif_Rahman Werewolf (IOI18_werewolf) C++17
100 / 100
 1606 ms 217912 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target ("fma")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
 
const int lim = 6e5;
 
struct fenwick_tree{
    int n;
    vector<int> sm;
    fenwick_tree(int _n){
        n = _n;
        sm.assign(n, 0);
    }
    void upd(int in, int x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    int sum(int in){
        in++;
        int s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    int sum(int l, int r){
        l--;
        int s = sum(r);
        if(l >= 0) s-=sum(l);
        return s;
    }
};
 
struct reachability_tree{
    int n;
    vector<int> p;
    vector<vector<int>> v;
    vector<int> w;
    reachability_tree(int _n, int _w){
        n = _n;
        p.resize(n);
        v.resize(n);
        w.resize(n, _w);
        for(int i = 0; i < n; i++) p[i] = i;
    }
    inline int get(int x){
        if(p[x] != x) p[x] = get(p[x]);
        return p[x];
    }
    void unite(int a, int b, int _w){
        a = get(a), b = get(b);
        p[a] = n, p[b] = n;
        p.pb(n);
        v.pb({});
        v[n].pb(a);
        if(a != b) v[n].pb(b);
        w.pb(_w);
        n++;
    }
};
 
int n, m, q;
 
reachability_tree rtl(0, 0), rtr(0, 0);
 
int szl[lim], szr[lim], posl[lim], posr[lim];
vector<int> al, ar;
int ancl[lim][20], ancr[lim][20];
 
void dfsl(int nd, int ss){
    posl[nd] = al.size();
    szl[nd] = 0;
    if(rtl.v[nd].empty()){
        al.pb(nd);
        szl[nd] = 1;
        ancl[nd][0] = ss;
        return;
    }
    for(int x: rtl.v[nd]) if(x != ss) dfsl(x, nd);
    for(int x: rtl.v[nd]) szl[nd]+=szl[x];
    ancl[nd][0] = ss;
}
void dfsr(int nd, int ss){
    posr[nd] = ar.size();
    szr[nd] = 0;
    if(rtr.v[nd].empty()){
        ar.pb(nd);
        szr[nd] = 1;
        ancr[nd][0] = ss;
        return;
    }
    for(int x: rtr.v[nd]) if(x != ss) dfsr(x, nd);
    for(int x: rtr.v[nd]) szr[nd]+=szr[x];
    ancr[nd][0] = ss;
}
 
inline int bsl(int nd, int vl){
    if(ancl[nd][0] == -1 || rtl.w[ancl[nd][0]] > vl) return nd;
    for(int i = 1; i < 20; i++) if(ancl[nd][i] == -1 || rtl.w[ancl[nd][i]] > vl) return bsl(ancl[nd][i-1], vl);
    return bsl(ancl[nd][19], vl);
}
inline int bsr(int nd, int vl){
    if(ancr[nd][0] == -1 || rtr.w[ancr[nd][0]] < vl) return nd;
    for(int i = 1; i < 20; i++) if(ancr[nd][i] == -1 || rtr.w[ancr[nd][i]] < vl) return bsr(ancr[nd][i-1], vl);
    return bsr(ancr[nd][19], vl);
}
 
vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> ss, vector<int> ee, vector<int> L, vector<int> R){
    ::n = n, m = U.size(), q = ss.size();
    pair<int, int> edgel[m], edger[m];
    for(int i = 0; i < m; i++)  edgel[i] = {U[i], V[i]}, edger[i] = {U[i], V[i]};
 
    sort(edgel, edgel+m, [&](pair<int, int> a, pair<int, int> b){
        return max(a.f, a.sc) < max(b.f, b.sc);
    });
    sort(edger, edger+m, [&](pair<int, int> a, pair<int, int> b){
        return min(a.f, a.sc) > min(b.f, b.sc);
    });
 
    rtl = reachability_tree(n, 0), rtr = reachability_tree(n, n+1);
    for(int i = 0; i < m; i++) rtl.unite(edgel[i].f, edgel[i].sc, max(edgel[i].f, edgel[i].sc)), rtr.unite(edger[i].f, edger[i].sc, min(edger[i].f, edger[i].sc));
    for(int i = 0; i < rtl.n; i++) for(int j = 0; j < 20; j++) ancl[i][j] = -1;
    for(int i = 0; i < rtr.n; i++) for(int j = 0; j < 20; j++) ancr[i][j] = -1;
    dfsl(rtl.n-1, -1);
    dfsr(rtr.n-1, -1);
 
    for(int i = 1; i < 20; i++) for(int j = 0; j < rtl.n; j++){
        if(ancl[j][i-1] == -1) continue;
        ancl[j][i] = ancl[ancl[j][i-1]][i-1];
    }
    for(int i = 1; i < 20; i++) for(int j = 0; j < rtr.n; j++){
        if(ancr[j][i-1] == -1) continue;
        ancr[j][i] = ancr[ancr[j][i-1]][i-1];
    }
 
    vector<int> ans(q, 0);
 
    pair<int, int> points[n];
    for(int i = 0; i < n; i++) points[i] = {posl[i], posr[i]};
    sort(points, points+n);
 
    vector<tuple<int, int, int>> query1[n], query2[n];
 
    for(int qq = 0; qq < q; qq++){
        int ndl = bsl(ee[qq], R[qq]), ndr = bsr(ss[qq], L[qq]);
        int l1 = posl[ndl], r1 = posl[ndl]+szl[ndl]-1;
        int l2 = posr[ndr], r2 = posr[ndr]+szr[ndr]-1;
        query1[max(l1, r1)].pb({min(l2, r2), max(l2, r2), qq});
        if(min(l1, r1) > 0) query2[min(l1, r1)-1].pb({min(l2, r2), max(l2, r2), qq});
    }
 
    fenwick_tree bit(n);
    int inx = 0;
 
    for(int i = 0; i < n; i++){
        while(inx < n && points[inx].f == i){
            bit.upd(points[inx].sc, 1);
            inx++;
        }
        for(auto [r1, r2, in]: query1[i]){
            ans[in]+=bit.sum(r1, r2);
        }
        for(auto [r1, r2, in]: query2[i]){
            ans[in]-=bit.sum(r1, r2);
        }
    }
 
    for(int &x: ans) x = min(x, 1);
 
    return ans;
}

Compilation message

werewolf.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
werewolf.cpp:8: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
werewolf.cpp:9: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 9 ms 2732 KB Output is correct
11 Correct 8 ms 2508 KB Output is correct
12 Correct 8 ms 2508 KB Output is correct
13 Correct 10 ms 2764 KB Output is correct
14 Correct 9 ms 2536 KB Output is correct
15 Correct 12 ms 3560 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 149588 KB Output is correct
2 Correct 1173 ms 149172 KB Output is correct
3 Correct 1004 ms 148900 KB Output is correct
4 Correct 888 ms 148768 KB Output is correct
5 Correct 862 ms 148816 KB Output is correct
6 Correct 870 ms 149172 KB Output is correct
7 Correct 822 ms 148024 KB Output is correct
8 Correct 1044 ms 149292 KB Output is correct
9 Correct 845 ms 149148 KB Output is correct
10 Correct 666 ms 147772 KB Output is correct
11 Correct 719 ms 148772 KB Output is correct
12 Correct 725 ms 148628 KB Output is correct
13 Correct 1184 ms 149732 KB Output is correct
14 Correct 1165 ms 149588 KB Output is correct
15 Correct 1190 ms 149440 KB Output is correct
16 Correct 1190 ms 149456 KB Output is correct
17 Correct 813 ms 147660 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 9 ms 2732 KB Output is correct
11 Correct 8 ms 2508 KB Output is correct
12 Correct 8 ms 2508 KB Output is correct
13 Correct 10 ms 2764 KB Output is correct
14 Correct 9 ms 2536 KB Output is correct
15 Correct 12 ms 3560 KB Output is correct
16 Correct 916 ms 149588 KB Output is correct
17 Correct 1173 ms 149172 KB Output is correct
18 Correct 1004 ms 148900 KB Output is correct
19 Correct 888 ms 148768 KB Output is correct
20 Correct 862 ms 148816 KB Output is correct
21 Correct 870 ms 149172 KB Output is correct
22 Correct 822 ms 148024 KB Output is correct
23 Correct 1044 ms 149292 KB Output is correct
24 Correct 845 ms 149148 KB Output is correct
25 Correct 666 ms 147772 KB Output is correct
26 Correct 719 ms 148772 KB Output is correct
27 Correct 725 ms 148628 KB Output is correct
28 Correct 1184 ms 149732 KB Output is correct
29 Correct 1165 ms 149588 KB Output is correct
30 Correct 1190 ms 149440 KB Output is correct
31 Correct 1190 ms 149456 KB Output is correct
32 Correct 813 ms 147660 KB Output is correct
33 Correct 1024 ms 149640 KB Output is correct
34 Correct 1325 ms 184160 KB Output is correct
35 Correct 1247 ms 157148 KB Output is correct
36 Correct 994 ms 152096 KB Output is correct
37 Correct 1177 ms 153812 KB Output is correct
38 Correct 1069 ms 154844 KB Output is correct
39 Correct 1069 ms 152064 KB Output is correct
40 Correct 1606 ms 217060 KB Output is correct
41 Correct 991 ms 150536 KB Output is correct
42 Correct 798 ms 150452 KB Output is correct
43 Correct 1499 ms 185952 KB Output is correct
44 Correct 1140 ms 153048 KB Output is correct
45 Correct 1062 ms 156056 KB Output is correct
46 Correct 992 ms 153380 KB Output is correct
47 Correct 1216 ms 151740 KB Output is correct
48 Correct 1169 ms 150176 KB Output is correct
49 Correct 1161 ms 151724 KB Output is correct
50 Correct 1151 ms 150276 KB Output is correct
51 Correct 1431 ms 217912 KB Output is correct
52 Correct 1450 ms 217908 KB Output is correct