oj.uz

Submission #870914

# Submission time Handle Problem Language Result Execution time Memory
870914 2023-11-09T12:57:51 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1604 ms 48692 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;

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)
{
    if (reg[a] != cur) mp[cur][reg[a]] = mp[cur][reg[a]] + seen;
    for (ll 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) mp1[cur][reg[a]]= mp[cur][reg[a]] + dp[a];
}

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, -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; 
        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:108: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]
  108 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:108: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]
  108 |         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 12 ms 10584 KB Output is correct
7 Correct 16 ms 10840 KB Output is correct
8 Correct 20 ms 10840 KB Output is correct
9 Correct 25 ms 11352 KB Output is correct
10 Correct 44 ms 11864 KB Output is correct
11 Correct 64 ms 12308 KB Output is correct
12 Correct 79 ms 13088 KB Output is correct
13 Correct 91 ms 13776 KB Output is correct
14 Correct 110 ms 14852 KB Output is correct
15 Correct 143 ms 17700 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 557 ms 20248 KB Output isn't correct
2 Incorrect 673 ms 19912 KB Output isn't correct
3 Incorrect 1025 ms 24584 KB Output isn't correct
4 Correct 153 ms 14592 KB Output is correct
5 Correct 209 ms 15976 KB Output is correct
6 Correct 440 ms 16524 KB Output is correct
7 Correct 611 ms 18952 KB Output is correct
8 Correct 693 ms 26392 KB Output is correct
9 Correct 1030 ms 31704 KB Output is correct
10 Correct 1427 ms 35640 KB Output is correct
11 Correct 1604 ms 35724 KB Output is correct
12 Incorrect 710 ms 33320 KB Output isn't correct
13 Incorrect 861 ms 34776 KB Output isn't correct
14 Incorrect 1079 ms 36144 KB Output isn't correct
15 Incorrect 1391 ms 40600 KB Output isn't correct
16 Incorrect 1429 ms 48692 KB Output isn't correct
17 Incorrect 1433 ms 48384 KB Output isn't correct