oj.uz

Submission #870940

# Submission time Handle Problem Language Result Execution time Memory
870940 2023-11-09T14:08:36 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1633 ms 48420 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)
{
    if (reg[a] != curi) 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];
    }
    dp[a] += (reg[a] == curi);
    if (cur != reg[a] && idx[reg[a]].size() < B) mp1[cur][reg[a]] = mp1[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; 
        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:109: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]
  109 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:109: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]
  109 |         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 5 ms 10584 KB Output is correct
6 Correct 10 ms 10836 KB Output is correct
7 Correct 15 ms 10840 KB Output is correct
8 Correct 16 ms 10840 KB Output is correct
9 Correct 24 ms 11352 KB Output is correct
10 Correct 49 ms 11864 KB Output is correct
11 Correct 65 ms 12296 KB Output is correct
12 Correct 71 ms 13168 KB Output is correct
13 Correct 98 ms 13852 KB Output is correct
14 Correct 116 ms 14848 KB Output is correct
15 Correct 149 ms 17700 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 20252 KB Execution killed with signal 13
2 Runtime error 55 ms 19908 KB Execution killed with signal 13
3 Runtime error 57 ms 24588 KB Execution killed with signal 13
4 Correct 138 ms 14592 KB Output is correct
5 Correct 213 ms 15980 KB Output is correct
6 Correct 452 ms 16524 KB Output is correct
7 Correct 624 ms 18952 KB Output is correct
8 Correct 581 ms 26384 KB Output is correct
9 Correct 1008 ms 31760 KB Output is correct
10 Correct 1426 ms 35640 KB Output is correct
11 Correct 1633 ms 35724 KB Output is correct
12 Incorrect 707 ms 33320 KB Output isn't correct
13 Incorrect 879 ms 34768 KB Output isn't correct
14 Runtime error 317 ms 36248 KB Execution killed with signal 13
15 Runtime error 163 ms 40624 KB Execution killed with signal 13
16 Runtime error 151 ms 48420 KB Execution killed with signal 13
17 Runtime error 157 ms 48296 KB Execution killed with signal 13