oj.uz

Submission #870896

# Submission time Handle Problem Language Result Execution time Memory
870896 2023-11-09T12:18:56 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1803 ms 70208 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define pii pair<int, int>
#define mpr make_pair
#define fi first
#define se second
#define all(v) v.begin(), v.end()

const int MXN = 2e5 + 5;
const int B = 2000;

int n, r, q;
int reg[MXN], p[MXN];
vector<int> idx[MXN];
vector<pii> v1[MXN];
vector<int> v2[MXN];
vector<int> adj[MXN];
int dp[MXN];
int in[MXN], out[MXN];
int tim = -1;
int cur = -1;
map<pii, int> mp;

void dfs(int a, int p)
{
    in[a] = ++tim;
    for (int v : adj[a])
    {
        if (v == p) continue;
        dfs(v, a);
    }
    out[a] = ++tim;
}

void dfs1(int a, int p, int seen)
{
    if (reg[a] != cur) mp[mpr(cur, reg[a])] += seen;
    for (int v : adj[a])
    {
        if (v == p) continue;
        dfs1(v, a, seen + (reg[a] == cur));
        dp[a] += dp[v];
    }
    dp[a] += (reg[a] == cur);
    if (cur != reg[a] && idx[reg[a]].size() < B) mp[mpr(reg[a], cur)] += dp[a];
}

int main()
{
    cin >> n >> r >> q;
    cin >> reg[1];
    idx[reg[1]].pb(1);
    for (int i = 2; i <= n; i++)
    {
        cin >> p[i] >> reg[i];
        adj[p[i]].pb(i);
        idx[reg[i]].pb(i);
    }
    dfs(1, 1);
    for (int i = 1; i <= r; i++)
    {
        for (int x : idx[i])
        {
            v1[i].pb(mpr(in[x], 1));
            v1[i].pb(mpr(out[x] + 1, -1));
            v2[i].pb(in[x]);
        }
        sort(all(v1[i]));
        sort(all(v2[i]));
    }
    for (int i = 1; i <= r; i++)
    {
        if (idx[i].size() < B) continue; 
        cur = i;
        dfs1(1, 1, 0);
    }
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (mp.find(mpr(u, v)) != mp.end())
        {
            cout << mp[mpr(u, v)] << endl;
            continue;
        }
        int i = 0;
        int j = 0;
        int ans = 0;
        int rn = 0;
        while (i < v1[u].size() && j < v2[v].size())
        {
            if (v1[u][i].fi <= v2[v][j]) rn += v1[u][i++].se;
            else 
            {
                ans += rn;
                j++;
            }
        }
        mp[mpr(u, v)] = ans;
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:93:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while (i < v1[u].size() && j < v2[v].size())
      |                                    ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 4 ms 21412 KB Output is correct
3 Correct 5 ms 21416 KB Output is correct
4 Correct 6 ms 21428 KB Output is correct
5 Correct 7 ms 21964 KB Output is correct
6 Correct 15 ms 22104 KB Output is correct
7 Correct 19 ms 22364 KB Output is correct
8 Correct 22 ms 22088 KB Output is correct
9 Correct 36 ms 23160 KB Output is correct
10 Correct 54 ms 23480 KB Output is correct
11 Correct 67 ms 24200 KB Output is correct
12 Correct 79 ms 24880 KB Output is correct
13 Correct 107 ms 24444 KB Output is correct
14 Correct 119 ms 25068 KB Output is correct
15 Correct 143 ms 28380 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 598 ms 30880 KB Output isn't correct
2 Incorrect 692 ms 29260 KB Output isn't correct
3 Incorrect 1043 ms 36560 KB Output isn't correct
4 Correct 168 ms 26760 KB Output is correct
5 Correct 231 ms 28244 KB Output is correct
6 Correct 383 ms 28280 KB Output is correct
7 Correct 569 ms 28976 KB Output is correct
8 Correct 638 ms 37200 KB Output is correct
9 Correct 1110 ms 43808 KB Output is correct
10 Correct 1561 ms 49640 KB Output is correct
11 Correct 1770 ms 47496 KB Output is correct
12 Incorrect 899 ms 42140 KB Output isn't correct
13 Incorrect 1066 ms 45324 KB Output isn't correct
14 Incorrect 1326 ms 47296 KB Output isn't correct
15 Incorrect 1604 ms 59128 KB Output isn't correct
16 Incorrect 1803 ms 70208 KB Output isn't correct
17 Incorrect 1746 ms 69260 KB Output isn't correct