oj.uz

Submission #870948

# Submission time Handle Problem Language Result Execution time Memory
870948 2023-11-09T15:03:15 Z aykhn Regions (IOI09_regions) C++17
100 / 100
 1597 ms 48424 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define pii pair<ll, ll>
#define mpr make_pair
#define fi first
#define se second
#define all(v) v.begin(), v.end()
 
const ll MXN = 2e5 + 5;
const ll MXR = 25e3 + 5;
const ll B = 3000;
 
ll n, r, q;
ll reg[MXN], p[MXN];
vector<ll> idx[MXR];
vector<pii> v1[MXR];
vector<ll> v2[MXR];
vector<ll> adj[MXN];
ll id[MXR], dp[MXN], in[MXN], out[MXN];
vector<vector<ll>> mp, mp1;
ll tim = -1;
ll cur = -1, curi = -1;
 
void dfs(ll a, ll p)
{
    in[a] = ++tim;
    for (ll v : adj[a])
    {
        if (v == p) continue;
        dfs(v, a);
    }
    out[a] = ++tim;
}
 
void dfs1(ll a, ll p, ll seen)
{
    dp[a] = 0;
    mp[cur][reg[a]] = mp[cur][reg[a]] + seen;
    for (ll v : adj[a])
    {
        if (v == p) continue;
        dfs1(v, a, seen + (reg[a] == curi));
        dp[a] += dp[v];
    }
    mp1[cur][reg[a]] = mp1[cur][reg[a]] + dp[a];
    dp[a] += (reg[a] == curi);
}
 
signed main()
{
    cin >> n >> r >> q;
    cin >> reg[1];
    idx[reg[1]].pb(1);
    for (ll i = 2; i <= n; i++)
    {
        cin >> p[i] >> reg[i];
        adj[p[i]].pb(i);
        adj[i].pb(p[i]);
        idx[reg[i]].pb(i);
    }
    dfs(1, 1);
    for (ll i = 1; i <= r; i++)
    {
        for (ll x : idx[i])
        {
            v1[i].pb(mpr(in[x], 1));
            v1[i].pb(mpr(out[x], -1));
            v2[i].pb(in[x]);
        }
        sort(all(v1[i]));
        sort(all(v2[i]));
    }
    ll cnt = 0;
    for (ll i = 1; i <= r; i++)
    {
        if (idx[i].size() < B) continue; 
        id[i] = cnt++;
    }
    mp.resize(cnt + 1, vector<ll> (r + 1, 0));
    mp1.resize(cnt + 1, vector<ll> (r + 1, 0));
    for (ll i = 1; i <= r; i++)
    {
        if (idx[i].size() < B) continue; 
        curi = i;
        cur = id[i];
        dfs1(1, 1, 0);
    }
    while (q--)
    {
        ll u, v;
        cin >> u >> v;
        if (idx[u].size() >= B)
        {
            cout << mp[id[u]][v] << endl;
            continue;
        }
        if (idx[v].size() >= B)
        {
            cout << ""<<mp1[id[v]][u] << endl;
            continue;
        }
        ll i = 0;
        ll j = 0;
        ll ans = 0;
        ll 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:110: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]
  110 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:110: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]
  110 |         while (i < v1[u].size() && j < v2[v].size())
      |                                    ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 9 ms 10840 KB Output is correct
7 Correct 15 ms 10840 KB Output is correct
8 Correct 21 ms 10840 KB Output is correct
9 Correct 25 ms 11352 KB Output is correct
10 Correct 50 ms 11864 KB Output is correct
11 Correct 65 ms 12528 KB Output is correct
12 Correct 79 ms 13080 KB Output is correct
13 Correct 94 ms 13836 KB Output is correct
14 Correct 112 ms 14844 KB Output is correct
15 Correct 134 ms 17704 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 21704 KB Output is correct
2 Correct 651 ms 21328 KB Output is correct
3 Correct 987 ms 24584 KB Output is correct
4 Correct 165 ms 14588 KB Output is correct
5 Correct 219 ms 15988 KB Output is correct
6 Correct 466 ms 16528 KB Output is correct
7 Correct 638 ms 18956 KB Output is correct
8 Correct 598 ms 26384 KB Output is correct
9 Correct 1002 ms 31712 KB Output is correct
10 Correct 1402 ms 35636 KB Output is correct
11 Correct 1597 ms 35728 KB Output is correct
12 Correct 761 ms 33320 KB Output is correct
13 Correct 909 ms 34772 KB Output is correct
14 Correct 1095 ms 36144 KB Output is correct
15 Correct 1407 ms 40592 KB Output is correct
16 Correct 1445 ms 48424 KB Output is correct
17 Correct 1478 ms 48296 KB Output is correct