oj.uz

Submission #572250

# Submission time Handle Problem Language Result Execution time Memory
572250 2022-06-04T06:55:25 Z MadokaMagicaFan Werewolf (IOI18_werewolf) C++14
15 / 100
 884 ms 64248 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]);

        if (n > 3000) {
            ans[i] = isancup(pup,pdn);
            continue;
        }

        /* 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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 18 ms 39380 KB Output is correct
3 Correct 18 ms 39448 KB Output is correct
4 Correct 17 ms 39380 KB Output is correct
5 Correct 17 ms 39408 KB Output is correct
6 Correct 18 ms 39400 KB Output is correct
7 Correct 18 ms 39448 KB Output is correct
8 Correct 18 ms 39352 KB Output is correct
9 Correct 18 ms 39436 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 18 ms 39380 KB Output is correct
3 Correct 18 ms 39448 KB Output is correct
4 Correct 17 ms 39380 KB Output is correct
5 Correct 17 ms 39408 KB Output is correct
6 Correct 18 ms 39400 KB Output is correct
7 Correct 18 ms 39448 KB Output is correct
8 Correct 18 ms 39352 KB Output is correct
9 Correct 18 ms 39436 KB Output is correct
10 Correct 110 ms 39960 KB Output is correct
11 Correct 149 ms 39820 KB Output is correct
12 Correct 328 ms 39788 KB Output is correct
13 Correct 106 ms 39952 KB Output is correct
14 Correct 142 ms 39952 KB Output is correct
15 Correct 884 ms 39896 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 528 ms 64248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 18 ms 39380 KB Output is correct
3 Correct 18 ms 39448 KB Output is correct
4 Correct 17 ms 39380 KB Output is correct
5 Correct 17 ms 39408 KB Output is correct
6 Correct 18 ms 39400 KB Output is correct
7 Correct 18 ms 39448 KB Output is correct
8 Correct 18 ms 39352 KB Output is correct
9 Correct 18 ms 39436 KB Output is correct
10 Correct 110 ms 39960 KB Output is correct
11 Correct 149 ms 39820 KB Output is correct
12 Correct 328 ms 39788 KB Output is correct
13 Correct 106 ms 39952 KB Output is correct
14 Correct 142 ms 39952 KB Output is correct
15 Correct 884 ms 39896 KB Output is correct
16 Incorrect 528 ms 64248 KB Output isn't correct
17 Halted 0 ms 0 KB -