oj.uz

Submission #472122

# Submission time Handle Problem Language Result Execution time Memory
472122 2021-09-13T05:55:56 Z jwvg0425 Regions (IOI09_regions) C++17
30 / 100
 8000 ms 131076 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <fstream>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e9+7)

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int h[200005];
int par[200005];
int in[200005];
int out[200005];
int byIn[200005];
vector<int> byOut[200005];
vector<int> edge[200005];
vector<int> byH[200005];
map<ii, int> ans;
int t = 1;

void dfs(int root)
{
    in[root] = t;
    byIn[t] = root;
    for (auto& e : edge[root])
    {
        t++;
        dfs(e);
    }
    out[root] = t;
    byOut[t].push_back(root);
}

int query(int r1, int r2)
{
    vector<ii> ts;
    for (auto& x : byH[r1])
    {
        ts.emplace_back(in[x], -1);
        ts.emplace_back(out[x], 1);
    }

    for (auto& x : byH[r2])
        ts.emplace_back(in[x], 0);

    sort(all(ts));

    int res = 0;
    int cnt = 0;
    for (auto& ti : ts)
    {
        if (ti.yy == 0)
            res += cnt;
        else
            cnt -= ti.yy;
    }

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, r, q;
    cin >> n >> r >> q;

    cin >> h[1];
    byH[h[1]].push_back(1);

    for (int i = 2; i <= n; i++)
    {
        cin >> par[i] >> h[i];
        edge[par[i]].push_back(i);
        byH[h[i]].push_back(i);
    }

    dfs(1);
    
    for (int i = 1; i <= r; i++)
    {
        if (byH[i].size() < 450)
            continue;

        vector<int> cnts(r + 5);

        for (int c = 1; c <= n; c++)
        {
            int x = byIn[c];

            ans[{ i, h[x] }] += cnts[i];

            cnts[h[x]]++;

            ans[{ h[x], i }] += cnts[h[x]];

            for (auto& o : byOut[c])
                cnts[h[o]]--;
        }
    }

    for (int i = 0; i < q; i++)
    {
        int r1, r2;

        cin >> r1 >> r2;

        if (byH[r1].size() < 450 && byH[r2].size() < 450)
        {
            cout << query(r1, r2) << endl;
        }
        else
        {
            cout << ans[{ r1, r2 }] << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14408 KB Output is correct
2 Correct 9 ms 14408 KB Output is correct
3 Correct 10 ms 14408 KB Output is correct
4 Correct 12 ms 14408 KB Output is correct
5 Correct 20 ms 14408 KB Output is correct
6 Correct 29 ms 14408 KB Output is correct
7 Correct 41 ms 14408 KB Output is correct
8 Correct 44 ms 14536 KB Output is correct
9 Correct 74 ms 15012 KB Output is correct
10 Correct 125 ms 14920 KB Output is correct
11 Correct 226 ms 15304 KB Output is correct
12 Correct 244 ms 15816 KB Output is correct
13 Correct 333 ms 15816 KB Output is correct
14 Correct 554 ms 16200 KB Output is correct
15 Correct 505 ms 18880 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2070 ms 20032 KB Output isn't correct
2 Incorrect 2521 ms 19540 KB Output isn't correct
3 Incorrect 4334 ms 21848 KB Output isn't correct
4 Correct 542 ms 16328 KB Output is correct
5 Correct 526 ms 17920 KB Output is correct
6 Incorrect 2353 ms 63624 KB Output isn't correct
7 Incorrect 3576 ms 36504 KB Output isn't correct
8 Runtime error 5237 ms 131076 KB Execution killed with signal 9
9 Correct 4608 ms 24884 KB Output is correct
10 Runtime error 3763 ms 131076 KB Execution killed with signal 9
11 Execution timed out 8063 ms 26744 KB Time limit exceeded
12 Incorrect 2352 ms 30044 KB Output isn't correct
13 Incorrect 3450 ms 30656 KB Output isn't correct
14 Incorrect 6177 ms 74064 KB Output isn't correct
15 Incorrect 6424 ms 36724 KB Output isn't correct
16 Incorrect 5154 ms 42044 KB Output isn't correct
17 Incorrect 7946 ms 84840 KB Output isn't correct