Submission #605419

#	Time	Username	Problem	Language	Result	Execution time	Memory
605419		AmirElarbi	Werewolf (IOI18_werewolf)	C++14	34 / 100	943 ms	36800 KiB

werewolf

#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
typedef complex<int> Point;
//#define X real()
//#define Y imag()
#include "werewolf.h"
vi fin, adj[nax];
ii st[nax*4];
int ind[nax];
void dfs(int u, int p){
    fin.pb(u);
    for(auto x : adj[u]){
        if(x == p) continue;
        dfs(x,u);
    }
}
void build(int v,int l, int r){
    if(l ==r) {
        st[v].fi = st[v].se = fin[l];
        return;
    }
    int md = (l+r)/2;
    build(v*2, l, md);
    build(v*2+1, md+1, r);
    st[v].fi = max(st[v*2].fi, st[v*2+1].fi);
    st[v].se = min(st[v*2].se, st[v*2+1].se);
}
int query(int v, int l, int r, int i, int j, int ind){
    if(i > j) swap(i,j);
    if(r < i ||l > j) {
        if(ind) return INF;
        else return 0;
    }
    if(i <= l && r <= j){
        if(ind) return st[v].se;
        else return st[v].fi;
    }
    int md = (l+r)/2;
    if(!ind) return max(query(v*2,l,md,i,j,ind), query(v*2+1, md+1, r, i, j, ind));
    else return min(query(v*2,l,md,i,j,ind), query(v*2+1, md+1, r, i, j, ind));
}
bool vis[nax][2];
bool dfs2(int u, int end, int l, int r, bool ind){
    vis[u][ind] = 1;
    if(u == end) return ind;
    bool p = false;
    for(auto x : adj[u]){
        if(vis[x]) continue;
        if(ind == 1 && u <= r) p |= dfs2(x,end,l,r,ind);
        if(ind == 0 && u <= r && l <= u) p |= dfs2(x,end,l,r,1);
        if(ind == 0 && l <= u) p |= dfs2(x,end,l,r,0);
        if(p) break;
    }
    return p;
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi low,vi high) {

    int m = x.size();
    for (int i = 0; i < m; ++i)
    {
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }
    int q = s.size();
    vi a(q);
    if(n <=3000 && m<=6000 && q<=3000){
        for (int i = 0; i < q; ++i)
        {
            memset(vis,0,sizeof vis);
            if(dfs2(s[i], e[i], low[i], high[i],0)) a[i] = 1;
            else a[i] = 0;
        }
        return a;
    }
    for (int i = 0; i < n; ++i)
    {
        if(adj[i].size() == 1){
            dfs(i,i);
            break;
        }
    }
    build(1,0,n-1);
    for (int i = 0; i < n; ++i)
    {
        ind[fin[i]] = i;
    }
    
    for (int i = 0; i < q; ++i) {
        int l = min(ind[e[i]],ind[s[i]]), r = max(ind[e[i]],ind[s[i]])+1;
        while(l < r){
            int md = (l+r)/2;
            int mn = query(1,0,n-1, ind[s[i]], md, 1), mx = query(1,0,n-1, md, ind[e[i]], 0);
            //cout << mn << " " << mx << " " << md << endl;
            if(mn < low[i] && mx > high[i]){
                a[i] = 0;
                break;
            } else if(mn < low[i]){
                if(ind[s[i]] < ind[e[i]]) r = md;
                else l = md+1;
            } else if(mx > high[i]) {
                if(ind[s[i]] < ind[e[i]]) l = md+1;
                else r = md;
            } else{
                if(mx >= low[i] || mn <= high[i]) a[i] = 1;
                else a[i] = 0;
                break;
            }
        }
    }
    return a;
}

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