oj.uz

Submission #968124

# Submission time Handle Problem Language Result Execution time Memory
968124 2024-04-23T07:49:42 Z VinhLuu Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 332012 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
//const int mod = 1e9 + 7;
//const int oo = 1e9;

int n, q, cal[N], ans[N];
vector<int> p[N];

struct tree{
    int pa[N], sz[N], Min[N], Max[N], in[N], en[N], demin, be[N], f[N][22];
    vector<int> g[N];
    void pre(){
        for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1, Max[i] = Min[i] = i;
    }
    int fin(int u){
        return pa[u] == u ? u : pa[u] = fin(pa[u]);
    }
    bool dsu(int x,int y){
        x = fin(x);
        y = fin(y);
        if(x == y) return 0;
        if(sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        pa[y] = x;
        Max[x] = max(Max[x], Max[y]);
        Min[x] = min(Min[x], Min[y]);
        return 1;
    }
    void dfs(int u,int v){
        in[u] = ++demin;
        if(v == 0) for(int i = 0; i <= 18; i ++) f[u][i] = u;
        else{
            f[u][0] = v;
            for(int i = 1; i <= 18; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
        }
        be[demin] = u;
        for(auto j : g[u]){
            if(j == v) continue;
            dfs(j, u);
        }
        en[u] = demin;
    }
    bool kt(int u,int v){
        return in[u] <= in[v] && in[v] <= en[u];
    }
    int Find(int type, int x,int lim){
        if(type == 0){
            int kq = x;
            for(int i = 18; i >= 0; i --) if(f[x][i] <= lim){
                kq = f[x][i];
                x = f[x][i];
            }
            return kq;
        }else{
            int kq = x;
            for(int i = 18; i >= 0; i --) if(f[x][i] >= lim){
                kq = f[x][i];
                x = f[x][i];
            }
            return kq;
        }
    }
} T[2];

vector<int> node[N], bit[N];
void fakeup(int x,int y){
    for(; x <= n; x += x & -x) node[x].pb(y);
}

void fakeget(int x,int y){
    for(; x > 0; x -= x & -x) node[x].pb(y);
}

void update(int x,int yy){
    for(; x <= n; x += x & -x){
        for(int y = upper_bound(all(node[x]), yy) - node[x].begin(); y <= node[x].size(); y += y & -y)
            bit[x][y]++;
    }
}

int get(int x,int yy){
    int ret = 0;
    for(; x > 0; x -= x & -x){
        for(int y = upper_bound(all(node[x]), yy) - node[x].begin(); y > 0; y -= y & -y)
            ret += bit[x][y];
    }
    return ret;
}

int query(int x,int y,int i,int j){
//    if(x == 4 && y == 4 && i == 4 && j == 5) cerr << get(y, j) << " " << get(x - 1, j) << " " << get(y, i - 1) << " " << get(x - 1, i - 1) << " fg\n";
    return get(y, j) - get(x - 1, j) - get(y, i - 1) + get(x - 1, i - 1);
}

vector<pii> open[N], close[N];

vector<int> check_validity(int _n, vector<int> X,vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    n = _n, q = L.size();
    for(int i = 0; i < X.size(); i ++){
        int x = ++X[i], y = ++Y[i];
        p[x].pb(y);
        p[y].pb(x);
//        cerr << x << " " << y << " k\n";
    }
    T[0].pre(), T[1].pre();
    for(int i = 1; i <= n; i ++) for(auto j : p[i]) if(j < i){
        int tmp = T[0].Max[T[0].fin(j)];
        if(T[0].dsu(i, j)){
            T[0].g[i].pb(tmp);
//            cerr << i << " " << tmp << " inc\n";
        }
    }
//    cerr << " ggg\n";
    T[0].dfs(n, 0);
    for(int i = n; i >= 1; i --) for(auto j : p[i]) if(j > i){
        int tmp = T[1].Min[T[1].fin(j)];
        if(T[1].dsu(i, j)){
            T[1].g[i].pb(tmp);
//            cerr << i << " " << tmp << "dec\n";
        }
    }
    T[1].dfs(1, 0);
//    for(int i = 1; i <= n; i ++) cerr << i << " " << T[0].in[i] << " " << T[0].en[i]<< " " << T[1].in[i] << " " << T[1].en[i] << " j\n";
    for(int i = 0; i < q; i ++){
        int s = ++S[i], e = ++E[i], l = ++L[i], r = ++R[i];
        if(e > R[i] || s < l){
            ans[i] = 0;
            continue;
        }
        int ce = T[0].Find(0, e, r), cs = T[1].Find(1, s, l);
//        cerr << s << " " << e << " " << l << " " << r << " " << cs << " " << ce << " " << T[1].in[cs] << " " << T[1].en[cs] << " " << L[i] << " " << R[i] << " t\n";
        open[T[0].in[ce] - 1].pb({i, cs});
        close[T[0].en[ce]].pb({i, cs});
        fakeget(T[1].in[cs] - 1, l - 1);
        fakeget(T[1].in[cs] - 1, r);
        fakeget(T[1].en[cs], l - 1);
        fakeget(T[1].en[cs], r);
//        cerr << T[1].in[cs] - 1 << " " << l - 1 << " up\n";
//        cerr << T[1].in[cs] - 1 << " " << r << " up\n";
//        cerr << T[1].en[cs] << " " << l - 1 << " up\n";
//        cerr << T[1].en[cs] << " " << r << " up\n";
    }
    for(int i = 1; i <= n; i ++){
        fakeup(T[1].in[i], i);
//        cerr << T[1].in[i] << " " << i << " uu\n";
    }
    for(int i = 1; i <= n; i ++){
        sort(all(node[i]));
        node[i].resize(unique(all(node[i])) - node[i].begin());
//        cout << i << " pp\n";
//        for(auto j : node[i]) cout << j << " ";
//        cout << "\n";
        bit[i].pb(0);
        for(auto j : node[i]) bit[i].pb(0);
    }
    for(int i = 1; i <= n; i ++){
        int u = T[0].be[i];
        update(T[1].in[u], u);
//        cerr << T[1].in[u] << " " << u << " y\n";
//        cerr << get(3, 5) << " hghg\n";
        for(auto [id, j] : open[i]){
            int tmp =  query(T[1].in[j], T[1].en[j], L[id], R[id]);;
//            cerr << id << " " << j << " " << tmp << " d\n";
            cal[id] -= query(T[1].in[j], T[1].en[j], L[id], R[id]);
        }
        for(auto [id, j] : close[i]){
            int tmp = query(T[1].in[j], T[1].en[j], L[id], R[id]);
//            cerr << id << " " << j << " " << tmp << " " << T[1].in[j] << " " << T[1].en[j] << " " << L[id] << " " << R[id] << " i\n";
            cal[id] += query(T[1].in[j], T[1].en[j], L[id], R[id]);
        }
    }
    vector<int> out;
    for(int i = 0; i < q; i ++){
//        cerr << cal[i] << " ";
        if(!cal[i]) out.pb(0);
        else out.pb(1);
    }
//    cerr << "h\n";
    return out;
}

//#define lpv
#ifdef lpv

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    vector<int> x, y, st, ed, lf, rt;
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i <= m; i ++){
        int gg, hh; cin >> gg >> hh;
        x.pb(gg),y.pb(hh);
    }

    for(int i = 1; i <= q; i ++){
        int g, h, j, k; cin >> g >> h >> j >> k;
        st.pb(g), ed.pb(h), lf.pb(j), rt.pb(k);
    }
    vector<int> oo = check_validity(n,x,y,st,ed,lf,rt);
    for(auto j : oo) cout << j << "\n";
}

#endif // lpv

Compilation message

werewolf.cpp: In function 'void update(int, int)':
werewolf.cpp:89:72: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int y = upper_bound(all(node[x]), yy) - node[x].begin(); y <= node[x].size(); y += y & -y)
      |                                                                      ~~^~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 0; i < X.size(); i ++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:167:18: warning: unused variable 'j' [-Wunused-variable]
  167 |         for(auto j : node[i]) bit[i].pb(0);
      |                  ^
werewolf.cpp:175:17: warning: unused variable 'tmp' [-Wunused-variable]
  175 |             int tmp =  query(T[1].in[j], T[1].en[j], L[id], R[id]);;
      |                 ^~~
werewolf.cpp:180:17: warning: unused variable 'tmp' [-Wunused-variable]
  180 |             int tmp = query(T[1].in[j], T[1].en[j], L[id], R[id]);
      |                 ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 168276 KB Output is correct
2 Correct 70 ms 168380 KB Output is correct
3 Correct 53 ms 168804 KB Output is correct
4 Correct 52 ms 168964 KB Output is correct
5 Correct 61 ms 169020 KB Output is correct
6 Correct 60 ms 168788 KB Output is correct
7 Correct 52 ms 168788 KB Output is correct
8 Correct 52 ms 168816 KB Output is correct
9 Correct 53 ms 168792 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 168276 KB Output is correct
2 Correct 70 ms 168380 KB Output is correct
3 Correct 53 ms 168804 KB Output is correct
4 Correct 52 ms 168964 KB Output is correct
5 Correct 61 ms 169020 KB Output is correct
6 Correct 60 ms 168788 KB Output is correct
7 Correct 52 ms 168788 KB Output is correct
8 Correct 52 ms 168816 KB Output is correct
9 Correct 53 ms 168792 KB Output is correct
10 Correct 75 ms 170884 KB Output is correct
11 Correct 70 ms 170856 KB Output is correct
12 Correct 71 ms 171088 KB Output is correct
13 Correct 68 ms 171140 KB Output is correct
14 Correct 68 ms 171352 KB Output is correct
15 Correct 63 ms 170816 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2812 ms 330880 KB Output is correct
2 Correct 3344 ms 330700 KB Output is correct
3 Correct 3418 ms 328464 KB Output is correct
4 Correct 3442 ms 325900 KB Output is correct
5 Correct 3259 ms 324300 KB Output is correct
6 Correct 3038 ms 331080 KB Output is correct
7 Correct 1499 ms 304428 KB Output is correct
8 Correct 3525 ms 332012 KB Output is correct
9 Correct 1330 ms 294532 KB Output is correct
10 Correct 2798 ms 312380 KB Output is correct
11 Correct 3703 ms 317864 KB Output is correct
12 Correct 2720 ms 315188 KB Output is correct
13 Execution timed out 4025 ms 328788 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 168276 KB Output is correct
2 Correct 70 ms 168380 KB Output is correct
3 Correct 53 ms 168804 KB Output is correct
4 Correct 52 ms 168964 KB Output is correct
5 Correct 61 ms 169020 KB Output is correct
6 Correct 60 ms 168788 KB Output is correct
7 Correct 52 ms 168788 KB Output is correct
8 Correct 52 ms 168816 KB Output is correct
9 Correct 53 ms 168792 KB Output is correct
10 Correct 75 ms 170884 KB Output is correct
11 Correct 70 ms 170856 KB Output is correct
12 Correct 71 ms 171088 KB Output is correct
13 Correct 68 ms 171140 KB Output is correct
14 Correct 68 ms 171352 KB Output is correct
15 Correct 63 ms 170816 KB Output is correct
16 Correct 2812 ms 330880 KB Output is correct
17 Correct 3344 ms 330700 KB Output is correct
18 Correct 3418 ms 328464 KB Output is correct
19 Correct 3442 ms 325900 KB Output is correct
20 Correct 3259 ms 324300 KB Output is correct
21 Correct 3038 ms 331080 KB Output is correct
22 Correct 1499 ms 304428 KB Output is correct
23 Correct 3525 ms 332012 KB Output is correct
24 Correct 1330 ms 294532 KB Output is correct
25 Correct 2798 ms 312380 KB Output is correct
26 Correct 3703 ms 317864 KB Output is correct
27 Correct 2720 ms 315188 KB Output is correct
28 Execution timed out 4025 ms 328788 KB Time limit exceeded
29 Halted 0 ms 0 KB -