oj.uz

Submission #472120

# Submission time Handle Problem Language Result Execution time Memory
472120 2021-09-13T05:44:10 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(n + 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 8 ms 14416 KB Output is correct
3 Correct 10 ms 14408 KB Output is correct
4 Correct 12 ms 14408 KB Output is correct
5 Correct 16 ms 14408 KB Output is correct
6 Correct 18 ms 14408 KB Output is correct
7 Correct 48 ms 14408 KB Output is correct
8 Correct 28 ms 14536 KB Output is correct
9 Correct 79 ms 14996 KB Output is correct
10 Correct 115 ms 15036 KB Output is correct
11 Correct 181 ms 15304 KB Output is correct
12 Correct 156 ms 15820 KB Output is correct
13 Correct 330 ms 15816 KB Output is correct
14 Correct 480 ms 16284 KB Output is correct
15 Correct 464 ms 18888 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2397 ms 20516 KB Output isn't correct
2 Incorrect 2571 ms 19844 KB Output isn't correct
3 Incorrect 5110 ms 22096 KB Output isn't correct
4 Correct 506 ms 16328 KB Output is correct
5 Correct 587 ms 17984 KB Output is correct
6 Incorrect 2308 ms 63740 KB Output isn't correct
7 Incorrect 3459 ms 36700 KB Output isn't correct
8 Runtime error 5561 ms 131076 KB Execution killed with signal 9
9 Correct 5027 ms 24788 KB Output is correct
10 Runtime error 3746 ms 131076 KB Execution killed with signal 9
11 Execution timed out 8077 ms 26780 KB Time limit exceeded
12 Incorrect 2430 ms 30600 KB Output isn't correct
13 Incorrect 3304 ms 31180 KB Output isn't correct
14 Incorrect 6406 ms 74768 KB Output isn't correct
15 Incorrect 6354 ms 37400 KB Output isn't correct
16 Incorrect 5425 ms 42644 KB Output isn't correct
17 Execution timed out 8047 ms 85380 KB Time limit exceeded