Submission #243393

#	Time	Username	Problem	Language	Result	Execution time	Memory
243393		ant101	Werewolf (IOI18_werewolf)	C++14	15 / 100	316 ms	19960 KiB

werewolf

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include "werewolf.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
#define mp make_pair
#define f first
#define s second

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 6e3+5;
const ll INF = 1e18;
const ld PI = 4*atan((ld)1);
const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
ll vis[MX];
ll vis2[MX];
ll cl, cr;
vector<ll> adj[MX];

void dfs1(ll u) {
    trav(v, adj[u]) {
        if (!vis[v] && v>=cl) {
            vis[v] = true;
            dfs1(v);
        }
    }
}

void dfs2(ll u) {
    trav(v, adj[u]) {
        if (!vis2[v] && v<=cr) {
            vis2[v] = true;
            dfs2(v);
        }
    }
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();
    F0R (i, sz(X)) {
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    std::vector<int> A(Q);
    for (int i = 0; i < Q; ++i) {
        memset(vis, 0, sizeof(vis));
        memset(vis2, 0, sizeof(vis2));
        cl = L[i];
        cr = R[i];
        if (S[i]>=L[i]) {
            vis[S[i]] = true;
            dfs1(S[i]);
        }
        if (E[i]<=R[i]) {
            vis2[E[i]] = true;
            dfs2(E[i]);
        }
        bool cango = false;
        F0R (j, N) {
            if (vis[j] && vis2[j] && j >= cl && j <= cr) {
                cango = true;
                break;
            }
        }
        if (vis[E[i]]) {
            cango = true;
        }
        A[i] = cango;
    }
    return A;
}

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