oj.uz

답안 #1037428

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037428 2024-07-28T20:33:46 Z c2zi6 늑대인간 (IOI18_werewolf) C++14
15 / 100
 4000 ms 110888 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;
    }
}

struct DSU {
    int n;
    VI par;
    DSU(){}
    DSU(int n_arg) : n(n_arg) {
        par = VI(n);
        rep(u, n) par[u] = u;
    }
    int get(int u) {
        return u == par[u] ? u : (par[u] = get(par[u]));
    }
    bool onion(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) return false;
        par[v] = u;
        return true;
    }
} dsu;

struct COMPTREE {
    int n;
    VVI par;
    VVI gp;
    VI tin, tout;
    VI euler;
    int tc;
    COMPTREE(){}
    COMPTREE(int n_arg) : n(n_arg) {
        par = VVI(n, VI(20, -1));
        gp = VVI(n);
        tin = tout = VI(n);
    }
    void dfs(int u) {
        euler.pb(u);
        tin[u] = tc++;
        for (int v : gp[u]) dfs(v);
        tout[u] = tc-1;
    }
    void init() {
        replr(i, 1, 19) rep(u, n) par[u][i] = par[par[u][i-1]][i-1];
        int root;
        rep(u, n) {
            if (par[u][0] == u) root = u;
            else gp[par[u][0]].pb(u);
        }
        tc = 0;
        dfs(root);
        cout << endl;
    }
    int lift(int u, int L, int R) {
        reprl(i, 19, 0) if (L <= par[u][i] && par[u][i] <= R) u = par[u][i];
        return u;
    }
    void print() {
        rep(u, n) cout << u << "'s parent: " << par[u][0] << endl;
        for (int u : euler) cout << u << " "; cout << endl;
    }
    void print(int u) {
        replr(i, tin[u], tout[u]) cout << euler[i] << " ";
        cout << endl;
    }
} lwp, hgp;

VI check_validity(int N, VI X, VI Y, VI S, VI E, VI L, VI R) {
    int n = N;
    VVI gp(n);
    rep(i, X.size()) {
        gp[X[i]].pb(Y[i]);
        gp[Y[i]].pb(X[i]);
    }
    lwp = hgp = COMPTREE(n);
    dsu = DSU(n);
    replr(u, 0, n-1) for (int v : gp[u]) if (v < u) {
        if (dsu.onion(u, v = dsu.get(v))) lwp.par[v][0] = u;
    }
    lwp.par[n-1][0] = n-1;
    lwp.init();
    dsu = DSU(n);
    reprl(u, n-1, 0) for (int v : gp[u]) if (v > u) {
        if (dsu.onion(u, v = dsu.get(v))) hgp.par[v][0] = u;
    }
    hgp.par[0][0] = 0;
    hgp.init();

    VI ans;
    rep(i, S.size()) {
        int u = hgp.lift(S[i], L[i], +2e9);
        int v = lwp.lift(E[i], -2e9, R[i]);

        set<int> st;
        replr(i, hgp.tin[u], hgp.tout[u]) st.insert(hgp.euler[i]);
        replr(i, lwp.tin[v], lwp.tout[v]) if (st.count(lwp.euler[i])) goto answertrue;
        ans.pb(false);
        continue;
        answertrue:
        ans.pb(true);
    }
    return ans;
}

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 member function 'void COMPTREE::print()':
werewolf.cpp:123:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  123 |         for (int u : euler) cout << u << " "; cout << endl;
      |         ^~~
werewolf.cpp:123:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  123 |         for (int u : euler) cout << u << " "; cout << endl;
      |                                               ^~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 282 ms 2064 KB Output is correct
11 Correct 215 ms 1880 KB Output is correct
12 Correct 15 ms 1880 KB Output is correct
13 Correct 147 ms 2140 KB Output is correct
14 Correct 13 ms 2140 KB Output is correct
15 Correct 257 ms 2092 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3751 ms 109672 KB Output is correct
2 Execution timed out 4054 ms 110888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 282 ms 2064 KB Output is correct
11 Correct 215 ms 1880 KB Output is correct
12 Correct 15 ms 1880 KB Output is correct
13 Correct 147 ms 2140 KB Output is correct
14 Correct 13 ms 2140 KB Output is correct
15 Correct 257 ms 2092 KB Output is correct
16 Correct 3751 ms 109672 KB Output is correct
17 Execution timed out 4054 ms 110888 KB Time limit exceeded
18 Halted 0 ms 0 KB -