oj.uz

Submission #870901

# Submission time Handle Problem Language Result Execution time Memory
870901 2023-11-09T12:26:48 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1782 ms 80680 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 5 ms 22976 KB Output is correct
2 Correct 5 ms 22872 KB Output is correct
3 Correct 5 ms 23276 KB Output is correct
4 Correct 6 ms 23288 KB Output is correct
5 Correct 8 ms 23340 KB Output is correct
6 Correct 14 ms 23404 KB Output is correct
7 Correct 21 ms 23784 KB Output is correct
8 Correct 21 ms 23856 KB Output is correct
9 Correct 34 ms 24432 KB Output is correct
10 Correct 50 ms 25464 KB Output is correct
11 Correct 77 ms 26076 KB Output is correct
12 Correct 84 ms 26968 KB Output is correct
13 Correct 111 ms 27280 KB Output is correct
14 Correct 121 ms 27884 KB Output is correct
15 Correct 156 ms 31416 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 33580 KB Execution killed with signal 13
2 Runtime error 85 ms 31172 KB Execution killed with signal 13
3 Runtime error 157 ms 39604 KB Execution killed with signal 13
4 Correct 172 ms 28564 KB Output is correct
5 Correct 224 ms 31040 KB Output is correct
6 Correct 388 ms 31320 KB Output is correct
7 Correct 563 ms 33044 KB Output is correct
8 Correct 627 ms 43252 KB Output is correct
9 Correct 1160 ms 52816 KB Output is correct
10 Correct 1561 ms 58188 KB Output is correct
11 Correct 1782 ms 56572 KB Output is correct
12 Incorrect 915 ms 51916 KB Output isn't correct
13 Incorrect 1160 ms 55232 KB Output isn't correct
14 Runtime error 471 ms 52108 KB Execution killed with signal 13
15 Runtime error 314 ms 63036 KB Execution killed with signal 13
16 Runtime error 305 ms 80680 KB Execution killed with signal 13
17 Runtime error 373 ms 78740 KB Execution killed with signal 13