oj.uz

Submission #968114

# Submission time Handle Problem Language Result Execution time Memory
968114 2024-04-23T07:45:01 Z VinhLuu Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 293324 KB 
#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 = 6e5 + 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:87:72: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         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:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i = 0; i < X.size(); i ++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:165:18: warning: unused variable 'j' [-Wunused-variable]
  165 |         for(auto j : node[i]) bit[i].pb(0);
      |                  ^
werewolf.cpp:173:17: warning: unused variable 'tmp' [-Wunused-variable]
  173 |             int tmp =  query(T[1].in[j], T[1].en[j], L[id], R[id]);;
      |                 ^~~
werewolf.cpp:178:17: warning: unused variable 'tmp' [-Wunused-variable]
  178 |             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 27 ms 119640 KB Output is correct
2 Correct 27 ms 119644 KB Output is correct
3 Correct 25 ms 117592 KB Output is correct
4 Correct 29 ms 119644 KB Output is correct
5 Correct 25 ms 117704 KB Output is correct
6 Correct 26 ms 119644 KB Output is correct
7 Correct 26 ms 117596 KB Output is correct
8 Correct 26 ms 119644 KB Output is correct
9 Correct 26 ms 119644 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 119640 KB Output is correct
2 Correct 27 ms 119644 KB Output is correct
3 Correct 25 ms 117592 KB Output is correct
4 Correct 29 ms 119644 KB Output is correct
5 Correct 25 ms 117704 KB Output is correct
6 Correct 26 ms 119644 KB Output is correct
7 Correct 26 ms 117596 KB Output is correct
8 Correct 26 ms 119644 KB Output is correct
9 Correct 26 ms 119644 KB Output is correct
10 Correct 42 ms 119636 KB Output is correct
11 Correct 44 ms 119832 KB Output is correct
12 Correct 43 ms 121636 KB Output is correct
13 Correct 41 ms 119636 KB Output is correct
14 Correct 42 ms 121856 KB Output is correct
15 Correct 38 ms 121684 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2835 ms 284320 KB Output is correct
2 Correct 3468 ms 285284 KB Output is correct
3 Correct 3396 ms 284656 KB Output is correct
4 Correct 3618 ms 283464 KB Output is correct
5 Correct 3282 ms 287812 KB Output is correct
6 Correct 2943 ms 293324 KB Output is correct
7 Correct 1565 ms 267916 KB Output is correct
8 Correct 3371 ms 290188 KB Output is correct
9 Correct 1313 ms 257288 KB Output is correct
10 Correct 2745 ms 275868 KB Output is correct
11 Correct 3597 ms 279160 KB Output is correct
12 Correct 2686 ms 275260 KB Output is correct
13 Execution timed out 4035 ms 289240 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 119640 KB Output is correct
2 Correct 27 ms 119644 KB Output is correct
3 Correct 25 ms 117592 KB Output is correct
4 Correct 29 ms 119644 KB Output is correct
5 Correct 25 ms 117704 KB Output is correct
6 Correct 26 ms 119644 KB Output is correct
7 Correct 26 ms 117596 KB Output is correct
8 Correct 26 ms 119644 KB Output is correct
9 Correct 26 ms 119644 KB Output is correct
10 Correct 42 ms 119636 KB Output is correct
11 Correct 44 ms 119832 KB Output is correct
12 Correct 43 ms 121636 KB Output is correct
13 Correct 41 ms 119636 KB Output is correct
14 Correct 42 ms 121856 KB Output is correct
15 Correct 38 ms 121684 KB Output is correct
16 Correct 2835 ms 284320 KB Output is correct
17 Correct 3468 ms 285284 KB Output is correct
18 Correct 3396 ms 284656 KB Output is correct
19 Correct 3618 ms 283464 KB Output is correct
20 Correct 3282 ms 287812 KB Output is correct
21 Correct 2943 ms 293324 KB Output is correct
22 Correct 1565 ms 267916 KB Output is correct
23 Correct 3371 ms 290188 KB Output is correct
24 Correct 1313 ms 257288 KB Output is correct
25 Correct 2745 ms 275868 KB Output is correct
26 Correct 3597 ms 279160 KB Output is correct
27 Correct 2686 ms 275260 KB Output is correct
28 Execution timed out 4035 ms 289240 KB Time limit exceeded
29 Halted 0 ms 0 KB -