Submission #378386

#	Time	Username	Problem	Language	Result	Execution time	Memory
378386		rocks03	Werewolf (IOI18_werewolf)	C++14	15 / 100	4024 ms	29952 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;
    }
}

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:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

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