oj.uz

답안 #572249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572249 2022-06-04T06:53:33 Z MadokaMagicaFan 늑대인간 (IOI18_werewolf) C++14
15 / 100
 4000 ms 72608 KB 
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 2e5;
const int K = 13;
vector<int> adj[N];

struct node {
    int p;
    vector<int> c;
    int j[K];
    int d;
};

node up[N];
node dn[N];

int getpup(int x) { return up[x].p = (x == up[x].p) ? x : getpup(up[x].p); };
int getpdn(int x) { return dn[x].p = (x == dn[x].p) ? x : getpdn(dn[x].p); };

void
mergeup(int x, int y)
{
    if (getpup(x) == y)
        return;
    up[y].c.pb(getpup(x));
    up[getpup(x)].p = y;
}

void
mergedn(int x, int y)
{
    if (getpdn(x) == y)
        return;
    dn[y].c.pb(getpdn(x));
    dn[getpdn(x)].p = y;
}

void
dfsup(int x)
{
    up[x].j[0] = up[x].p;
    for (int u : up[x].c) {
        up[u].p = x;
        up[u].d = up[x].d+1;
        dfsup(u);
    }
    return;
}

void
dfsdn(int x)
{
    dn[x].j[0] = dn[x].p;
    for (int u : dn[x].c) {
        dn[u].p = x;
        dn[u].d = dn[x].d+1;
        dfsdn(u);
    }
    return;
}

int
getup(int u, int x)
{
    for (int j = K-1; j >= 0; --j) {
        if (up[u].j[j] <= x)
            u = up[u].j[j];
    }
    return u;
}

int
getdn(int u, int x)
{
    for (int j = K-1; j >= 0; --j) {
        if (dn[u].j[j] >= x)
            u = dn[u].j[j];
    }
    return u;
}

bool
isancup(int x, int y)
{
    if (up[y].d < up[x].d) return 0;
    if (y == x) return 1;

    for (int j = K-1; j >= 0; --j) {
        if (up[up[y].j[j]].d >= up[x].d)
            y = up[y].j[j];
    }

    return x == y;
}

bool
isancdn(int x, int y)
{
    if (dn[y].d < dn[x].d) return 0;
    if (y == x) return 1;

    for (int j = K-1; j >= 0; --j) {
        if (dn[dn[y].j[j]].d >= dn[x].d)
            y = dn[y].j[j];
    }

    return x == y;
}


vector<int> 
check_validity(int n, vector<int> x, vector<int> y, 
        vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    vector<int> ans(sz(s),0);

    for (int i = 0; i < sz(x); ++i) {
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }

    for (int i = 0; i < n; ++i) {
        up[i].p = i;
        dn[i].p = i;
        up[i].d = 0;
        dn[i].d = 0;
    }

    for (int i = 0; i < n; ++i) {
        for (int x : adj[i]) {
            if (x > i) continue;
            mergeup(x,i);
        }
    }

    for (int i = n-1; i >= 0; --i) {
        for (int x : adj[i]) {
            if (x < i) continue;
            mergedn(x,i);
        }
    }

    int pup, pdn;

    dfsup(n-1);
    dfsdn(0);

    for (int j = 1; j < K; ++j) {
        for (int i = 0; i < n; ++i) {
            up[i].j[j] = up[up[i].j[j-1]].j[j-1];
            dn[i].j[j] = dn[dn[i].j[j-1]].j[j-1];
        }
    }

    /* for (int i = 0; i < n; ++i) { */
    /*     cout << "TST: " << i << ' ' << up[i].p; */
    /*     for (int j = 0; j < 3; ++j) { */
    /*         cout << ' ' << up[i].j[j]; */
    /*     } */
    /*     cout << endl; */
    /* } */
    /* for (int i = 0; i < n; ++i) { */
    /*     cout << "TST: " << i << ' ' << dn[i].p; */
    /*     for (int j = 0; j < 3; ++j) { */
    /*         cout << ' ' << dn[i].j[j]; */
    /*     } */
    /*     cout << endl; */
    /* } */

    for (int i = 0; i < sz(s); ++i) {
        pup = getup(e[i], r[i]);
        pdn = getdn(s[i], l[i]);

        /* cout << s[i] << ' ' << e[i] << ' ' << l[i] << ' '  << r[i] << endl; */
        /* cout << pup << ' ' << pdn << endl; */
        if (pup < l[i] || pdn > r[i]) continue;

        for (int j = l[i]; j <= r[i]; ++j) {
            if (isancup(pup,j) && isancdn(pdn,j)) {
                ans[i] = 1;
                break;
            }
        }
    }


    return ans;
}

#ifdef ONPC
void
solve()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> x(m);
    vector<int> y(m);
    vector<int> s(q);
    vector<int> e(q);
    vector<int> l(q);
    vector<int> r(q);
    for (int i = 0; i < m; ++i) cin >> x[i];
    for (int i = 0; i < m; ++i) cin >> y[i];
    for (int i = 0; i < q; ++i) cin >> s[i];
    for (int i = 0; i < q; ++i) cin >> e[i];
    for (int i = 0; i < q; ++i) cin >> l[i];
    for (int i = 0; i < q; ++i) cin >> r[i];

    vector<int> ans = check_validity(n,x,y,s,e,l,r);

    for (int a : ans) {
        cout << a << ' ';
    }
    cout << endl;
}

int32_t
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    freopen("in", "r", stdin);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39428 KB Output is correct
3 Correct 19 ms 39444 KB Output is correct
4 Correct 19 ms 39380 KB Output is correct
5 Correct 20 ms 39444 KB Output is correct
6 Correct 19 ms 39440 KB Output is correct
7 Correct 23 ms 39452 KB Output is correct
8 Correct 19 ms 39428 KB Output is correct
9 Correct 19 ms 39436 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39428 KB Output is correct
3 Correct 19 ms 39444 KB Output is correct
4 Correct 19 ms 39380 KB Output is correct
5 Correct 20 ms 39444 KB Output is correct
6 Correct 19 ms 39440 KB Output is correct
7 Correct 23 ms 39452 KB Output is correct
8 Correct 19 ms 39428 KB Output is correct
9 Correct 19 ms 39436 KB Output is correct
10 Correct 109 ms 39936 KB Output is correct
11 Correct 162 ms 39912 KB Output is correct
12 Correct 351 ms 39896 KB Output is correct
13 Correct 107 ms 40000 KB Output is correct
14 Correct 168 ms 40048 KB Output is correct
15 Correct 892 ms 40052 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4025 ms 72608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39428 KB Output is correct
3 Correct 19 ms 39444 KB Output is correct
4 Correct 19 ms 39380 KB Output is correct
5 Correct 20 ms 39444 KB Output is correct
6 Correct 19 ms 39440 KB Output is correct
7 Correct 23 ms 39452 KB Output is correct
8 Correct 19 ms 39428 KB Output is correct
9 Correct 19 ms 39436 KB Output is correct
10 Correct 109 ms 39936 KB Output is correct
11 Correct 162 ms 39912 KB Output is correct
12 Correct 351 ms 39896 KB Output is correct
13 Correct 107 ms 40000 KB Output is correct
14 Correct 168 ms 40048 KB Output is correct
15 Correct 892 ms 40052 KB Output is correct
16 Execution timed out 4025 ms 72608 KB Time limit exceeded
17 Halted 0 ms 0 KB -