oj.uz

Submission #870897

# Submission time Handle Problem Language Result Execution time Memory
870897 2023-11-09T12:21:26 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1827 ms 66164 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 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:94: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]
   94 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:94:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         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 21336 KB Output is correct
2 Correct 5 ms 21408 KB Output is correct
3 Correct 6 ms 21420 KB Output is correct
4 Correct 7 ms 21688 KB Output is correct
5 Correct 8 ms 21720 KB Output is correct
6 Correct 15 ms 22284 KB Output is correct
7 Correct 18 ms 22128 KB Output is correct
8 Correct 22 ms 21960 KB Output is correct
9 Correct 29 ms 23168 KB Output is correct
10 Correct 57 ms 23912 KB Output is correct
11 Correct 71 ms 23672 KB Output is correct
12 Correct 82 ms 24336 KB Output is correct
13 Correct 107 ms 24020 KB Output is correct
14 Correct 121 ms 25168 KB Output is correct
15 Correct 153 ms 27716 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 28612 KB Execution killed with signal 13
2 Runtime error 90 ms 26924 KB Execution killed with signal 13
3 Runtime error 150 ms 32208 KB Execution killed with signal 13
4 Correct 176 ms 25460 KB Output is correct
5 Correct 235 ms 28244 KB Output is correct
6 Correct 392 ms 28696 KB Output is correct
7 Correct 556 ms 29112 KB Output is correct
8 Correct 639 ms 37020 KB Output is correct
9 Correct 1069 ms 43412 KB Output is correct
10 Correct 1574 ms 50424 KB Output is correct
11 Correct 1827 ms 47328 KB Output is correct
12 Incorrect 1028 ms 42776 KB Output isn't correct
13 Incorrect 1177 ms 45580 KB Output isn't correct
14 Runtime error 512 ms 42616 KB Execution killed with signal 13
15 Runtime error 324 ms 51612 KB Execution killed with signal 13
16 Runtime error 330 ms 66164 KB Execution killed with signal 13
17 Runtime error 421 ms 63608 KB Execution killed with signal 13