Submission #378415

#	Time	Username	Problem	Language	Result	Execution time	Memory
378415		rocks03	Werewolf (IOI18_werewolf)	C++14	49 / 100	4048 ms	84192 KiB

werewolf

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
// #include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    int M = SZ(X), Q = SZ(S);
    if(M <= 10000 && Q <= 10000){
        vector<int> g[N];
        rep(i, 0, M){
            int u = X[i], v = Y[i];
            g[u].pb(v); g[v].pb(u);
        }
        vector<int> ans(Q);
        rep(i, 0, Q){
            int s = S[i], t = E[i], l = L[i], r = R[i];
            int v = s;
            queue<pii> q;
            vector<vector<bool>> vis(2, vector<bool>(N, false));
            q.push({s, 0}); vis[0][v] = true;
            while(!q.empty()){
                auto [v, k] = q.front();
                q.pop();
                if(k == 1 && v == t) break;
                if(l <= v && v <= r && !vis[1][v]){
                    vis[1][v] = true;
                    q.push({v, 1});
                }
                for(int u : g[v]){
                    if(!k && u >= l){
                        if(!vis[k][u]){
                            vis[k][u] = true; q.push({u, k});
                        }
                    } else if(k && u <= r){
                        if(!vis[k][u]){
                            vis[k][u] = true; q.push({u, k});
                        }
                    }
                }
            }
            ans[i] = (vis[1][t] == true);
        }
        return ans;
    }
    if(M == N - 1){
        vector<int> g[N];
        rep(i, 0, M){
            int u = X[i], v = Y[i];
            g[u].pb(v); g[v].pb(u);
        }
        vector<int> a, p(N);
        rep(v, 0, N){
            if(SZ(g[v]) == 1){
                a.pb(v);
                p[a.back()] = SZ(a) - 1;
                while(SZ(a) < N){
                    v = a.back();
                    for(int u : g[v]){
                        if(SZ(a) == 1 || u != a[SZ(a) - 2]){
                            a.pb(u); p[a.back()] = SZ(a) - 1;
                            break;
                        }
                    }
                }
                break;
            }
        }
        const int MAXK = 20;
        int mnl[MAXK][N], mnr[MAXK][N], mxl[MAXK][N], mxr[MAXK][N];
        rep(i, 0, N){
            if(i > 0){
                mnl[0][i] = min(a[i - 1], a[i]);
                mxl[0][i] = max(a[i - 1], a[i]);
            }
            if(i < N - 1){
                mnr[0][i] = min(a[i], a[i + 1]);
                mxr[0][i] = max(a[i], a[i + 1]);
            }
        }
        rep(k, 0, MAXK - 1){
            rep(i, 0, N){
                if(i + (1 << (k + 1)) < N){
                    mnr[k + 1][i] = min(mnr[k][i], mnr[k][i + (1 << k)]);
                    mxr[k + 1][i] = max(mxr[k][i], mxr[k][i + (1 << k)]);
                }
                if(i - (1 << (k + 1)) >= 0){
                    mnl[k + 1][i] = min(mnl[k][i], mnl[k][i - (1 << k)]);
                    mxl[k + 1][i] = max(mxl[k][i], mxl[k][i - (1 << k)]);
                }
            }
        }
        vector<int> ans(Q);
        rep(i, 0, Q){
            int s = S[i], t = E[i], l = L[i], r = R[i];
            int ls = p[s], rs = p[s], lt = p[t], rt = p[t];
            per(k, MAXK - 1, 0){
                if(ls - (1 << k) >= 0 && mnl[k][ls] >= l){
                    ls -= (1 << k);
                }
                if(rs + (1 << k) < N && mnr[k][rs] >= l){
                    rs += (1 << k);
                }
                if(lt - (1 << k) >= 0 && mxl[k][lt] <= r){
                    lt -= (1 << k);
                }
                if(rt + (1 << k) < N && mxr[k][rt] <= r){
                    rt += (1 << k);
                }
            }
            if(min(rs, rt) >= max(ls, lt)){
                ans[i] = 1;
            } else{
                ans[i] = 0;
            }
        }
        return ans;
    }
}

Compilation message (stderr)

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:37:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |                 auto [v, k] = q.front();
      |                      ^
werewolf.cpp:133:1: warning: control reaches end of non-void function [-Wreturn-type]
  133 | }
      | ^

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