oj.uz

Submission #870938

# Submission time Handle Problem Language Result Execution time Memory
870938 2023-11-09T14:05:52 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1592 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 endl '\n';
#define all(v) v.begin(), v.end()

const ll MXN = 2e5 + 5;
const ll MXR = 25e3 + 5;
const ll B = 5000;

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;
}

int curi;

void dfs1(ll a, ll p, ll seen)
{
    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);
    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);
        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:111: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]
  111 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:111: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]
  111 |         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 4 ms 10584 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 10 ms 10584 KB Output is correct
7 Correct 15 ms 10840 KB Output is correct
8 Correct 15 ms 10840 KB Output is correct
9 Correct 28 ms 11352 KB Output is correct
10 Correct 48 ms 11608 KB Output is correct
11 Correct 57 ms 12376 KB Output is correct
12 Correct 72 ms 13240 KB Output is correct
13 Correct 102 ms 13520 KB Output is correct
14 Correct 113 ms 14668 KB Output is correct
15 Correct 142 ms 17700 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 20108 KB Execution killed with signal 13
2 Runtime error 53 ms 18724 KB Execution killed with signal 13
3 Runtime error 57 ms 24580 KB Execution killed with signal 13
4 Correct 141 ms 14328 KB Output is correct
5 Correct 196 ms 15976 KB Output is correct
6 Correct 409 ms 16176 KB Output is correct
7 Correct 643 ms 18480 KB Output is correct
8 Correct 588 ms 26384 KB Output is correct
9 Correct 934 ms 31232 KB Output is correct
10 Correct 1387 ms 35616 KB Output is correct
11 Correct 1592 ms 32388 KB Output is correct
12 Incorrect 683 ms 33196 KB Output isn't correct
13 Incorrect 883 ms 33940 KB Output isn't correct
14 Runtime error 275 ms 34684 KB Execution killed with signal 13
15 Runtime error 150 ms 40576 KB Execution killed with signal 13
16 Runtime error 140 ms 48424 KB Execution killed with signal 13
17 Runtime error 148 ms 48300 KB Execution killed with signal 13