oj.uz

Submission #870903

# Submission time Handle Problem Language Result Execution time Memory
870903 2023-11-09T12:28:39 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1632 ms 80300 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++;
            }
        }
        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 22872 KB Output is correct
3 Correct 5 ms 22872 KB Output is correct
4 Correct 7 ms 22872 KB Output is correct
5 Correct 8 ms 22872 KB Output is correct
6 Correct 17 ms 23128 KB Output is correct
7 Correct 21 ms 23128 KB Output is correct
8 Correct 21 ms 23128 KB Output is correct
9 Correct 30 ms 23640 KB Output is correct
10 Correct 48 ms 23896 KB Output is correct
11 Correct 62 ms 24636 KB Output is correct
12 Correct 87 ms 25488 KB Output is correct
13 Correct 93 ms 25876 KB Output is correct
14 Correct 121 ms 26976 KB Output is correct
15 Correct 135 ms 30004 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 33572 KB Execution killed with signal 13
2 Runtime error 99 ms 31180 KB Execution killed with signal 13
3 Runtime error 160 ms 39600 KB Execution killed with signal 13
4 Correct 157 ms 26540 KB Output is correct
5 Correct 224 ms 28040 KB Output is correct
6 Correct 443 ms 28236 KB Output is correct
7 Correct 645 ms 30344 KB Output is correct
8 Correct 625 ms 38592 KB Output is correct
9 Correct 994 ms 43144 KB Output is correct
10 Correct 1435 ms 47020 KB Output is correct
11 Correct 1632 ms 43808 KB Output is correct
12 Incorrect 961 ms 48232 KB Output isn't correct
13 Incorrect 1163 ms 50216 KB Output isn't correct
14 Runtime error 457 ms 50580 KB Execution killed with signal 13
15 Runtime error 323 ms 63016 KB Execution killed with signal 13
16 Runtime error 309 ms 80300 KB Execution killed with signal 13
17 Runtime error 375 ms 78476 KB Execution killed with signal 13