oj.uz

Submission #870899

# Submission time Handle Problem Language Result Execution time Memory
870899 2023-11-09T12:22:19 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1784 ms 80312 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define pb push_back
#define pii pair<int, int>
#define mpr make_pair
#define fi first
#define se second
#define int ll
#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, ll> 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])] = 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)] = mp[mpr(reg[a], cur)] + dp[a];
}

signed 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;
        ll 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 = ans + rn;
                j++;
            }
        }
        mp[mpr(u, v)] = ans;
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:95:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:95:38: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         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 22872 KB Output is correct
2 Correct 6 ms 23020 KB Output is correct
3 Correct 6 ms 23024 KB Output is correct
4 Correct 7 ms 23032 KB Output is correct
5 Correct 8 ms 23596 KB Output is correct
6 Correct 14 ms 23456 KB Output is correct
7 Correct 20 ms 24268 KB Output is correct
8 Correct 22 ms 23764 KB Output is correct
9 Correct 30 ms 25060 KB Output is correct
10 Correct 58 ms 25144 KB Output is correct
11 Correct 71 ms 25788 KB Output is correct
12 Correct 85 ms 26432 KB Output is correct
13 Correct 102 ms 27508 KB Output is correct
14 Correct 122 ms 28376 KB Output is correct
15 Correct 146 ms 31028 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 33564 KB Execution killed with signal 13
2 Runtime error 83 ms 31172 KB Execution killed with signal 13
3 Runtime error 152 ms 39600 KB Execution killed with signal 13
4 Correct 164 ms 28548 KB Output is correct
5 Correct 234 ms 31184 KB Output is correct
6 Correct 361 ms 31260 KB Output is correct
7 Correct 541 ms 33204 KB Output is correct
8 Correct 634 ms 43628 KB Output is correct
9 Correct 1068 ms 52108 KB Output is correct
10 Correct 1506 ms 58308 KB Output is correct
11 Correct 1784 ms 57076 KB Output is correct
12 Incorrect 905 ms 51756 KB Output isn't correct
13 Incorrect 1076 ms 55192 KB Output isn't correct
14 Runtime error 437 ms 52856 KB Execution killed with signal 13
15 Runtime error 303 ms 63136 KB Execution killed with signal 13
16 Runtime error 300 ms 80312 KB Execution killed with signal 13
17 Runtime error 380 ms 78464 KB Execution killed with signal 13