oj.uz

답안 #1012547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012547 2024-07-02T10:23:29 Z c2zi6 늑대인간 (IOI18_werewolf) C++14
15 / 100
 381 ms 67664 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "werewolf.h"

namespace TEST2 {
    int n;
    VVI gp;
    void dfs(int u, VI& vis, int mn, int mx) {
        vis[u] = true;
        for (int v : gp[u]) if (!vis[v]) {
            if (mn <= v && v <= mx) {
                dfs(v, vis, mn, mx);
            }
        }
    }
    VI solve(int N, VI X, VI Y, VI S, VI E, VI L, VI R) {
        n = N;
        gp = VVI(n);
        rep(i, X.size()) {
            gp[X[i]].pb(Y[i]);
            gp[Y[i]].pb(X[i]);
        }
        VI ansret;
        rep(i, S.size()) {
            auto[s, e, l, r] = make_tuple(S[i], E[i], L[i], R[i]);
            VI visa, visb;
            visa = visb = VI(n);
            dfs(s, visa, l, +2e9);
            dfs(e, visb, -2e9, r);
            bool ans = false;
            rep(u, n) if (visa[u] && visb[u]) ans = true;
            ansret.pb(ans);
        }
        return ansret;
    }
}

namespace SPARSETABLE {
    const int MAXN = 2e5 + 30;
    const int MAXM = 20;
    int lg[MAXN];
    void initialize() {
        if (lg[0] == -1) return;
        lg[0] = -1;
        replr(i, 2, MAXN-1) lg[i] = lg[i/2]+1;
    }
    template<typename T, typename COMPORATOR>
    struct TABLE {
        T** arr;
        COMPORATOR comp;
        T best(T a, T b) {
            if (comp(a, b)) return a;
            return b;
        }
        template<typename ITERATOR>
        TABLE(ITERATOR begin, ITERATOR end) {
            initialize();
            int n = 0;
            for (ITERATOR it = begin; it != end; it++, n++);
            arr = new T*[n];
            rep(i, n) arr[i] = new T[MAXM];
            reprl(i, n-1, 0) {
                --end;
                arr[i][0] = *end;
                for (int j = 1; i+(1<<j) <= n; j++) {
                    arr[i][j] = best(arr[i][j-1], arr[i+(1<<(j-1))][j-1]);
                }
            }
        }
        T get(int l, int r) {
            int s = lg[r-l+1];
            return best(arr[l][s], arr[r-(1<<s)+1][s]);
        }
    };
};

namespace TEST3 {
    VI flatten(int N, VI X, VI Y) {
        int n = N;
        VVI gp(n);
        rep(i, X.size()) {
            gp[X[i]].pb(Y[i]);
            gp[Y[i]].pb(X[i]);
        }
        int s, e;
        s = -1;
        rep(u, n) if (gp[u].size() == 1) {
            if (s == -1) s = u;
            e = u;
        }
        int p = -1;
        int u = s;
        VI ret;
        ret.pb(u);
        while (u != e) {
            for (int v : gp[u]) if (v != p) {
                p = u;
                u = v;
                break;
            }
            ret.pb(u);
        }
        return ret;
    }
    VI solve(int N, VI X, VI Y, VI S, VI E, VI L, VI R) {
        VI a = flatten(N, X, Y);
        /*for (int x : a) cout << x << " "; cout << endl;*/
        VI idx(N);
        rep(i, N) idx[a[i]] = i;
        SPARSETABLE::TABLE<int, greater<int>> maxval(a.begin(), a.end());
        SPARSETABLE::TABLE<int, less<int>> minval(a.begin(), a.end());
        VI ansret;
        rep(i, S.size()) {
            auto[s, e, l, r] = make_tuple(S[i], E[i], L[i], R[i]);
            s = idx[s];
            e = idx[e];
            for (int i = 20; i >= 0; i--) {
                if (s+(1<<i) >= N) continue;
                if (minval.get(s, s+(1<<i)) >= l) s += (1<<i);
            }
            for (int i = 20; i >= 0; i--) {
                if (e-(1<<i) < 0) continue;
                if (maxval.get(e-(1<<i), e) <= r) e -= (1<<i);
            }
            ansret.pb(e <= s);
        }
        return ansret;
    }
};

VI check_validity(int N, VI X, VI Y, VI S, VI E, VI L, VI R) {
    int M = X.size();
    int Q = S.size();
    if (N <= 3000 && M <= 6000 && Q <= 3000) return TEST2::solve(N, X, Y, S, E, L, R);
    return TEST3::solve(N, X, Y, S, E, L, R);
}

Compilation message

werewolf.cpp: In function 'VI TEST2::solve(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:54:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |             auto[s, e, l, r] = make_tuple(S[i], E[i], L[i], R[i]);
      |                 ^
werewolf.cpp: In function 'VI TEST3::solve(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:143:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |             auto[s, e, l, r] = make_tuple(S[i], E[i], L[i], R[i]);
      |                 ^
werewolf.cpp: In function 'VI TEST3::flatten(int, VI, VI)':
werewolf.cpp:124:18: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |         while (u != e) {
      |                ~~^~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 155 ms 860 KB Output is correct
11 Correct 58 ms 956 KB Output is correct
12 Correct 15 ms 1116 KB Output is correct
13 Correct 167 ms 996 KB Output is correct
14 Correct 63 ms 856 KB Output is correct
15 Correct 160 ms 1124 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 381 ms 67664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 155 ms 860 KB Output is correct
11 Correct 58 ms 956 KB Output is correct
12 Correct 15 ms 1116 KB Output is correct
13 Correct 167 ms 996 KB Output is correct
14 Correct 63 ms 856 KB Output is correct
15 Correct 160 ms 1124 KB Output is correct
16 Incorrect 381 ms 67664 KB Output isn't correct
17 Halted 0 ms 0 KB -