oj.uz

Submission #870949

# Submission time Handle Problem Language Result Execution time Memory
870949 2023-11-09T15:05:19 Z aykhn Regions (IOI09_regions) C++17
100 / 100
 1624 ms 53628 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 = 600;
 
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 10680 KB Output is correct
5 Correct 4 ms 10584 KB Output is correct
6 Correct 12 ms 10840 KB Output is correct
7 Correct 18 ms 10840 KB Output is correct
8 Correct 18 ms 10840 KB Output is correct
9 Correct 30 ms 11352 KB Output is correct
10 Correct 48 ms 11864 KB Output is correct
11 Correct 60 ms 12344 KB Output is correct
12 Correct 79 ms 13068 KB Output is correct
13 Correct 86 ms 13816 KB Output is correct
14 Correct 116 ms 14852 KB Output is correct
15 Correct 136 ms 17700 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 21712 KB Output is correct
2 Correct 641 ms 21332 KB Output is correct
3 Correct 1002 ms 24620 KB Output is correct
4 Correct 156 ms 14588 KB Output is correct
5 Correct 204 ms 15980 KB Output is correct
6 Correct 464 ms 16532 KB Output is correct
7 Correct 630 ms 18944 KB Output is correct
8 Correct 633 ms 26392 KB Output is correct
9 Correct 1031 ms 31708 KB Output is correct
10 Correct 1399 ms 35636 KB Output is correct
11 Correct 1624 ms 35728 KB Output is correct
12 Correct 775 ms 33320 KB Output is correct
13 Correct 913 ms 34772 KB Output is correct
14 Correct 1362 ms 41156 KB Output is correct
15 Correct 1415 ms 40664 KB Output is correct
16 Correct 1484 ms 48420 KB Output is correct
17 Correct 1603 ms 53628 KB Output is correct