oj.uz

Submission #220797

# Submission time Handle Problem Language Result Execution time Memory
220797 2020-04-08T21:38:08 Z qkxwsm Regions (IOI09_regions) C++14
0 / 100
 112 ms 45820 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--;
        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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 15 ms 23872 KB Time limit exceeded (wall clock)
2 Execution timed out 15 ms 23808 KB Time limit exceeded (wall clock)
3 Execution timed out 15 ms 23808 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 23936 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 23936 KB Time limit exceeded (wall clock)
6 Execution timed out 15 ms 23936 KB Time limit exceeded (wall clock)
7 Execution timed out 15 ms 23936 KB Time limit exceeded (wall clock)
8 Execution timed out 16 ms 23936 KB Time limit exceeded (wall clock)
9 Execution timed out 16 ms 24448 KB Time limit exceeded (wall clock)
10 Execution timed out 18 ms 24448 KB Time limit exceeded (wall clock)
11 Execution timed out 19 ms 24832 KB Time limit exceeded (wall clock)
12 Execution timed out 21 ms 25344 KB Time limit exceeded (wall clock)
13 Execution timed out 23 ms 25088 KB Time limit exceeded (wall clock)
14 Execution timed out 28 ms 25728 KB Time limit exceeded (wall clock)
15 Execution timed out 28 ms 28288 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 38 ms 29048 KB Time limit exceeded (wall clock)
2 Execution timed out 40 ms 28032 KB Time limit exceeded (wall clock)
3 Execution timed out 42 ms 30972 KB Time limit exceeded (wall clock)
4 Execution timed out 25 ms 25728 KB Time limit exceeded (wall clock)
5 Execution timed out 28 ms 27392 KB Time limit exceeded (wall clock)
6 Execution timed out 34 ms 27132 KB Time limit exceeded (wall clock)
7 Execution timed out 49 ms 28408 KB Time limit exceeded (wall clock)
8 Execution timed out 51 ms 33528 KB Time limit exceeded (wall clock)
9 Execution timed out 79 ms 34608 KB Time limit exceeded (wall clock)
10 Execution timed out 83 ms 39544 KB Time limit exceeded (wall clock)
11 Execution timed out 103 ms 34888 KB Time limit exceeded (wall clock)
12 Execution timed out 112 ms 36088 KB Time limit exceeded (wall clock)
13 Execution timed out 96 ms 36216 KB Time limit exceeded (wall clock)
14 Execution timed out 104 ms 36088 KB Time limit exceeded (wall clock)
15 Execution timed out 92 ms 40568 KB Time limit exceeded (wall clock)
16 Execution timed out 93 ms 45820 KB Time limit exceeded (wall clock)
17 Execution timed out 91 ms 44536 KB Time limit exceeded (wall clock)