oj.uz

Submission #870900

# Submission time Handle Problem Language Result Execution time Memory
870900 2023-11-09T12:23:03 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1733 ms 80596 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 = 5000;

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 6 ms 22872 KB Output is correct
2 Correct 4 ms 23024 KB Output is correct
3 Correct 5 ms 23024 KB Output is correct
4 Correct 7 ms 23128 KB Output is correct
5 Correct 9 ms 23344 KB Output is correct
6 Correct 16 ms 23412 KB Output is correct
7 Correct 18 ms 23504 KB Output is correct
8 Correct 22 ms 23908 KB Output is correct
9 Correct 29 ms 24832 KB Output is correct
10 Correct 51 ms 25480 KB Output is correct
11 Correct 72 ms 25564 KB Output is correct
12 Correct 80 ms 26916 KB Output is correct
13 Correct 100 ms 27432 KB Output is correct
14 Correct 117 ms 27972 KB Output is correct
15 Correct 146 ms 30912 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 95 ms 31176 KB Execution killed with signal 13
3 Runtime error 87 ms 39604 KB Execution killed with signal 13
4 Correct 161 ms 29124 KB Output is correct
5 Correct 231 ms 31404 KB Output is correct
6 Correct 383 ms 31716 KB Output is correct
7 Correct 545 ms 32912 KB Output is correct
8 Correct 627 ms 43836 KB Output is correct
9 Correct 1078 ms 52208 KB Output is correct
10 Correct 1507 ms 58184 KB Output is correct
11 Correct 1733 ms 56632 KB Output is correct
12 Incorrect 899 ms 51860 KB Output isn't correct
13 Incorrect 1130 ms 55140 KB Output isn't correct
14 Runtime error 458 ms 52236 KB Execution killed with signal 13
15 Runtime error 306 ms 63028 KB Execution killed with signal 13
16 Runtime error 305 ms 80596 KB Execution killed with signal 13
17 Runtime error 370 ms 78468 KB Execution killed with signal 13