oj.uz

Submission #870915

# Submission time Handle Problem Language Result Execution time Memory
870915 2023-11-09T13:00:20 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1587 ms 48416 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));
            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 2 ms 10584 KB Output is correct
4 Correct 4 ms 10584 KB Output is correct
5 Correct 4 ms 10584 KB Output is correct
6 Correct 9 ms 10840 KB Output is correct
7 Correct 14 ms 10772 KB Output is correct
8 Correct 21 ms 10840 KB Output is correct
9 Correct 24 ms 11352 KB Output is correct
10 Correct 47 ms 11864 KB Output is correct
11 Correct 68 ms 12348 KB Output is correct
12 Correct 88 ms 13200 KB Output is correct
13 Correct 95 ms 13912 KB Output is correct
14 Correct 120 ms 14852 KB Output is correct
15 Correct 144 ms 17696 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 585 ms 20344 KB Output isn't correct
2 Incorrect 651 ms 19908 KB Output isn't correct
3 Incorrect 968 ms 24588 KB Output isn't correct
4 Correct 154 ms 14588 KB Output is correct
5 Correct 210 ms 15988 KB Output is correct
6 Correct 451 ms 16524 KB Output is correct
7 Correct 603 ms 18960 KB Output is correct
8 Correct 631 ms 26404 KB Output is correct
9 Correct 1018 ms 31712 KB Output is correct
10 Correct 1439 ms 35644 KB Output is correct
11 Correct 1587 ms 35724 KB Output is correct
12 Incorrect 708 ms 33324 KB Output isn't correct
13 Incorrect 891 ms 34944 KB Output isn't correct
14 Incorrect 1106 ms 36148 KB Output isn't correct
15 Incorrect 1398 ms 40600 KB Output isn't correct
16 Incorrect 1533 ms 48416 KB Output isn't correct
17 Incorrect 1425 ms 48300 KB Output isn't correct