oj.uz

Submission #870913

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

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 10668 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 4 ms 10584 KB Output is correct
5 Correct 6 ms 10584 KB Output is correct
6 Correct 11 ms 10836 KB Output is correct
7 Correct 13 ms 10840 KB Output is correct
8 Correct 19 ms 10840 KB Output is correct
9 Correct 26 ms 11352 KB Output is correct
10 Correct 46 ms 11864 KB Output is correct
11 Correct 73 ms 12300 KB Output is correct
12 Correct 74 ms 13168 KB Output is correct
13 Correct 96 ms 13848 KB Output is correct
14 Correct 114 ms 14844 KB Output is correct
15 Correct 138 ms 17704 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 577 ms 20252 KB Output isn't correct
2 Incorrect 661 ms 19912 KB Output isn't correct
3 Runtime error 73 ms 24596 KB Execution killed with signal 13
4 Correct 150 ms 14592 KB Output is correct
5 Correct 205 ms 15996 KB Output is correct
6 Correct 445 ms 16524 KB Output is correct
7 Correct 623 ms 18968 KB Output is correct
8 Correct 621 ms 26384 KB Output is correct
9 Correct 970 ms 31708 KB Output is correct
10 Correct 1366 ms 35632 KB Output is correct
11 Correct 1602 ms 35724 KB Output is correct
12 Incorrect 715 ms 33320 KB Output isn't correct
13 Incorrect 899 ms 34776 KB Output isn't correct
14 Incorrect 1070 ms 36144 KB Output isn't correct
15 Incorrect 1409 ms 40596 KB Output isn't correct
16 Incorrect 1480 ms 48424 KB Output isn't correct
17 Incorrect 1423 ms 48304 KB Output isn't correct