Submission #831548

#	Time	Username	Problem	Language	Result	Execution time	Memory
831548		ALeonidou	Werewolf (IOI18_werewolf)	C++17	34 / 100	1188 ms	55744 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define F first
#define S second
#define sz(x) (ll)x.size()
#define MID ((l+r)/2)
#define pb push_back
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
#define dbg4(x,y,z,w) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<" "<<#w<<": "<<w<<endl;
#define INF 1e9
typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;

void printVct(vi &v, string s =""){
    if (sz(s) > 0) cout<<s<<": ";
    for (ll i=0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

void tabb(ll n) {
    for (ll i= 0; i<n; i++) cout<<"\t";
}

vector <vi> adj;
ll n,m;
vi arr, inv, vis;

void dfs(ll u){
    vis[u] = 1;
    arr.pb(u);
    for (ll i=0; i<sz(adj[u]); i++){
        if (!vis[adj[u][i]]){
            dfs(adj[u][i]);
        }
    }
}

struct node{
    ll mini, maxi;
    node *L, *R;
    void build (ll l = 0, ll r = n-1){
        // tabb(tab);
        // dbg2(l,r);
        if (l == r){
            mini = arr[l];
            maxi = arr[l];
        } 
        else{
            L = new node;
            R = new node;
            L -> build (l, MID);
            R -> build (MID+1, r);
            mini =min(L->mini, R->mini);
            maxi =max(L->maxi, R->maxi);
        }
        // tabb(tab);
        // dbg2(mini, maxi);
    }

    ll queryMin(ll tl, ll tr, ll l = 0, ll r = n-1){
        if (l >= tl && r <= tr) return mini;
        else if (tl > r || tr < l) return INF;
        return min(L->queryMin(tl,tr,l,MID), R->queryMin(tl,tr,MID+1,r));
    }

    ll queryMax(ll tl, ll tr, ll l = 0, ll r = n-1){
        //dbg4(tl,tr,l,r);
        if (l >= tl && r <= tr) return maxi;
        else if (tl > r || tr < l) return -1;
        return max(L->queryMax(tl,tr,l,MID), R->queryMax(tl,tr,MID+1,r));
    }
};

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R){
    m = sz(X),n = N;
    vi deg(n, 0);
    adj.assign(n, vi());
    for (ll i=0;i<m; i++){
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
        deg[X[i]]++;
        deg[Y[i]]++;
    }

    //find start
    ll p = -1;
    for (ll i = 0; i<n; i++){
        if (deg[i] == 1){
            p =i;
            break;
        }
    }
    if (p == -1) return vi();

    //prepare arrays
    arr.clear(), inv.resize(n);
    vis.assign(n, 0);
    dfs(p);
    for (ll i= 0; i<n;i++){
        inv[arr[i]] = i; 
    }
    // printVct(arr, "arr");
    // printVct(inv,"inv");

    //build seg
    node root;
    root.build();

    //solve
    vi ans;
    ll q = sz(L);
    for (ll i=0; i<q; i++){
        ll s = S[i], e= E[i], tl = L[i], tr = R[i];
        ll idxS = inv[s], idxE = inv[e];
        // dbg2(idxS, idxE);

        if (idxS < idxE){
            // cout<<"INININII"<<endl;
            //dbg2(root.queryMin(3, 7), root.queryMax(4, 6));
            
            ll l = idxS, r = idxE, mid;
            ll L_idx = idxS;
            while (l <= r){
                mid = MID;
                // dbg3(l,r,mid);

                bool ok = (root.queryMin(l, mid) >= tl);
                // dbg(root.queryMin(l, mid));

                if (ok){
                    l = mid+1;
                    L_idx = mid;
                }
                else{
                    r = mid-1;
                }
            }

            // dbg(L_idx);

            if (root.queryMax(L_idx, idxE) <= tr){
                ans.pb(1);
                // cout<<"OK"<<endl;
            }
            else{
                ans.pb(0);
                // cout<<"NOT OK"<<endl;
            }
        }
        else{
            ll l = idxE, r = idxS, mid;
            ll R_idx = idxS;
            while (l <= r){
                mid = MID;
                // dbg3(l,r,mid);

                bool ok = (root.queryMin(mid, r) >= tl);
                // dbg(root.queryMin(mid, r));

                if (ok){
                    r = mid-1;
                    R_idx = mid;
                }
                else{
                    l = mid+1;
                }
            }

            // dbg(R_idx);
            // dbg(root.queryMax(idxE, R_idx));
            if (root.queryMax(idxE, R_idx) <= tr){
                ans.pb(1);
                // cout<<"OK"<<endl;
            }
            else{
                ans.pb(0);
                // cout<<"NOT OK"<<endl;
            }
        }
    }
    
    // cout<<endl;
    // printVct(ans, "ans");
    return ans;
}


/*

8 7 1
3 1
1 0
0 6
6 2
2 4
4 5
5 7
3 7 1 7

5 3 1 6



6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4

*/

Compilation message (stderr)

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:115:10: warning: 'root.node::R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |     node root;
      |          ^~~~
werewolf.cpp:115:10: warning: 'root.node::L' may be used uninitialized in this function [-Wmaybe-uninitialized]

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