oj.uz

Submission #220798

# Submission time Handle Problem Language Result Execution time Memory
220798 2020-04-08T21:47:29 Z qkxwsm Regions (IOI09_regions) C++14
100 / 100
 5349 ms 54660 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 200013;

int N, M, Q, T, K;
int parent[MAXN], arr[MAXN];
vi edge[MAXN];
int st[MAXN], ft[MAXN], loc[MAXN];
int ord[MAXN];
vi inds[MAXN], del[MAXN];
map<int, int> ans[MAXN];

void dfs(int u)
{
    st[u] = T;
    ft[u] = T;
    ord[T] = u;
    T++;
    inds[arr[u]].PB(st[u]);
    // cerr << "inds " << arr[u] << " PB " << st[u] << endl;
    for (int v : edge[u])
    {
        dfs(v);
        ft[u] = ft[v];
    }
    del[arr[u]].PB(ft[u]);
}
int order_of_key(vi &x, int n) //counts how many are strictly less than n.
{
    return LB(ALL(x), n) - x.begin();
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    // ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M >> Q;
    FOR(i, 0, N)
    {
        if (i)
        {
            cin >> parent[i];
            parent[i]--;
            edge[parent[i]].PB(i);
        }
        cin >> arr[i]; arr[i]--;
    }
    dfs(0);
    while(Q--)
    {
        int x, y;
        cin >> x >> y; x--; y--;
        // cerr << "wtf " << x << ' ' << y << endl;
        if (!ans[x].count(y))
        {
            //well shit.
            int res = 0;
            if (SZ(inds[x]) > SZ(inds[y]))
            {
                //for each node in y, count how many are in its parenthood.
                for (int c : inds[y])
                {
                    res += order_of_key(inds[x], c + 1) - order_of_key(del[x], c);
                }
            }
            else
            {
                //for each node in x, count how many y's are in its subtree.
                for (int c : inds[x])
                {
                    int u = ord[c];
                    // cerr << "u = " << u << endl;
                    res += order_of_key(inds[y], ft[u] + 1) - order_of_key(inds[y], st[u]);
                    // cerr << "res from " << u << " = " << ft[u] + 1 << ' ' << st[u] << endl;
                }
            }
            ans[x][y] = res;
        }
        cout << ans[x][y] << '\n';
        fflush(stdout);
        //how many are in subtree of some node of x.
        //x is smaller.
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 26 ms 23936 KB Output is correct
6 Correct 35 ms 24064 KB Output is correct
7 Correct 46 ms 24056 KB Output is correct
8 Correct 51 ms 24064 KB Output is correct
9 Correct 67 ms 24568 KB Output is correct
10 Correct 123 ms 24828 KB Output is correct
11 Correct 133 ms 25264 KB Output is correct
12 Correct 173 ms 25848 KB Output is correct
13 Correct 199 ms 25720 KB Output is correct
14 Correct 336 ms 26236 KB Output is correct
15 Correct 306 ms 29192 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 30520 KB Output is correct
2 Correct 1523 ms 29200 KB Output is correct
3 Correct 2494 ms 34104 KB Output is correct
4 Correct 283 ms 26872 KB Output is correct
5 Correct 397 ms 29048 KB Output is correct
6 Correct 588 ms 28908 KB Output is correct
7 Correct 802 ms 29400 KB Output is correct
8 Correct 1178 ms 36600 KB Output is correct
9 Correct 2292 ms 40616 KB Output is correct
10 Correct 4372 ms 47284 KB Output is correct
11 Correct 5349 ms 43488 KB Output is correct
12 Correct 1879 ms 39744 KB Output is correct
13 Correct 2348 ms 41696 KB Output is correct
14 Correct 3042 ms 42428 KB Output is correct
15 Correct 4132 ms 49040 KB Output is correct
16 Correct 4069 ms 54660 KB Output is correct
17 Correct 3922 ms 53140 KB Output is correct