oj.uz

Submission #870937

# Submission time Handle Problem Language Result Execution time Memory
870937 2023-11-09T14:05:02 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1605 ms 48424 KB 
#pragma comment(linker, "-Wl,--stack=268435456");
#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 = 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;
}

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:1: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    1 | #pragma comment(linker, "-Wl,--stack=268435456");
      | 
regions.cpp: In function 'int main()':
regions.cpp:112: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]
  112 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:112: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]
  112 |         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 6 ms 10680 KB Output is correct
6 Correct 11 ms 10584 KB Output is correct
7 Correct 16 ms 10840 KB Output is correct
8 Correct 18 ms 10840 KB Output is correct
9 Correct 27 ms 11352 KB Output is correct
10 Correct 49 ms 11604 KB Output is correct
11 Correct 62 ms 12376 KB Output is correct
12 Correct 84 ms 13216 KB Output is correct
13 Correct 90 ms 13496 KB Output is correct
14 Correct 120 ms 14668 KB Output is correct
15 Correct 131 ms 17712 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 20112 KB Execution killed with signal 13
2 Runtime error 55 ms 18792 KB Execution killed with signal 13
3 Runtime error 55 ms 24564 KB Execution killed with signal 13
4 Correct 140 ms 14324 KB Output is correct
5 Correct 219 ms 15976 KB Output is correct
6 Correct 454 ms 16112 KB Output is correct
7 Correct 643 ms 18484 KB Output is correct
8 Correct 580 ms 26384 KB Output is correct
9 Correct 962 ms 31236 KB Output is correct
10 Correct 1416 ms 35612 KB Output is correct
11 Correct 1605 ms 32388 KB Output is correct
12 Incorrect 723 ms 33188 KB Output isn't correct
13 Incorrect 893 ms 33944 KB Output isn't correct
14 Runtime error 284 ms 34668 KB Execution killed with signal 13
15 Runtime error 160 ms 40948 KB Execution killed with signal 13
16 Runtime error 141 ms 48424 KB Execution killed with signal 13
17 Runtime error 155 ms 48300 KB Execution killed with signal 13