Submission #968043

#	Time	Username	Problem	Language	Result	Execution time	Memory
968043		VinhLuu	Werewolf (IOI18_werewolf)	C++17	0 / 100	805 ms	524288 KiB

werewolf

#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 = 2e5 + 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 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});
        fakeup(T[1].in[cs] - 1, l - 1);
        fakeup(T[1].in[cs] - 1, r);
        fakeup(T[1].en[cs], l - 1);
        fakeup(T[1].en[cs], r);
    }
    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());
        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 << query(4, 4, 4, 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 << " ";
}

#endif // lpv

Compilation message (stderr)

werewolf.cpp: In function 'void update(int, int)':
werewolf.cpp:83:72: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         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:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 0; i < X.size(); i ++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:154:18: warning: unused variable 'j' [-Wunused-variable]
  154 |         for(auto j : node[i]) bit[i].pb(0);
      |                  ^
werewolf.cpp:162:17: warning: unused variable 'tmp' [-Wunused-variable]
  162 |             int tmp =  query(T[1].in[j], T[1].en[j], L[id], R[id]);;
      |                 ^~~
werewolf.cpp:167:17: warning: unused variable 'tmp' [-Wunused-variable]
  167 |             int tmp = query(T[1].in[j], T[1].en[j], L[id], R[id]);
      |                 ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51