oj.uz

Submission #870905

# Submission time Handle Problem Language Result Execution time Memory
870905 2023-11-09T12:35:19 Z aykhn Regions (IOI09_regions) C++17
45 / 100
 2837 ms 121860 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define pb push_back
#define pii pair<int, int>
#define mpr make_pair
#define fi first
#define se second
#define int ll
#define all(v) v.begin(), v.end()

const int MXN = 2e5 + 5;
const int B = 500;

int n, r, q;
int reg[MXN], p[MXN];
vector<int> idx[MXN];
vector<pii> v1[MXN];
vector<int> v2[MXN];
vector<int> adj[MXN];
int dp[MXN];
int in[MXN], out[MXN];
int tim = -1;
int cur = -1;
map<pii, ll> mp;

void dfs(int a, int p)
{
    in[a] = ++tim;
    for (int v : adj[a])
    {
        if (v == p) continue;
        dfs(v, a);
    }
    out[a] = ++tim;
}

void dfs1(int a, int p, int seen)
{
    if (reg[a] != cur) mp[mpr(cur, reg[a])] = mp[mpr(cur, reg[a])] + seen;
    for (int 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) mp[mpr(reg[a], cur)] = mp[mpr(reg[a], cur)] + dp[a];
}

signed main()
{
    cin >> n >> r >> q;
    cin >> reg[1];
    idx[reg[1]].pb(1);
    for (int i = 2; i <= n; i++)
    {
        cin >> p[i] >> reg[i];
        adj[p[i]].pb(i);
        idx[reg[i]].pb(i);
    }
    dfs(1, 1);
    for (int i = 1; i <= r; i++)
    {
        for (int 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]));
    }
    for (int i = 1; i <= r; i++)
    {
        if (idx[i].size() < B) continue; 
        cur = i;
        dfs1(1, 1, 0);
    }
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (mp.find(mpr(u, v)) != mp.end())
        {
            cout << mp[mpr(u, v)] << endl;
            continue;
        }
        int i = 0;
        int j = 0;
        ll ans = 0;
        int 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++;
            }
        }
        mp[mpr(u, v)] = ans;
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:95: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]
   95 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:95: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]
   95 |         while (i < v1[u].size() && j < v2[v].size())
      |                                    ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 4 ms 23024 KB Output is correct
3 Correct 5 ms 23280 KB Output is correct
4 Correct 7 ms 23284 KB Output is correct
5 Correct 8 ms 23336 KB Output is correct
6 Correct 17 ms 23404 KB Output is correct
7 Correct 23 ms 23752 KB Output is correct
8 Correct 20 ms 24136 KB Output is correct
9 Correct 31 ms 24688 KB Output is correct
10 Correct 53 ms 25232 KB Output is correct
11 Correct 76 ms 25796 KB Output is correct
12 Correct 84 ms 26848 KB Output is correct
13 Correct 102 ms 26864 KB Output is correct
14 Correct 119 ms 28596 KB Output is correct
15 Correct 152 ms 31172 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 33564 KB Execution killed with signal 13
2 Runtime error 203 ms 31388 KB Execution killed with signal 13
3 Runtime error 194 ms 39600 KB Execution killed with signal 13
4 Correct 177 ms 29324 KB Output is correct
5 Correct 227 ms 31420 KB Output is correct
6 Runtime error 443 ms 43788 KB Execution killed with signal 13
7 Correct 546 ms 33140 KB Output is correct
8 Runtime error 187 ms 49672 KB Execution killed with signal 13
9 Correct 1097 ms 52192 KB Output is correct
10 Correct 1570 ms 58220 KB Output is correct
11 Correct 1741 ms 56340 KB Output is correct
12 Incorrect 977 ms 51856 KB Output isn't correct
13 Incorrect 1133 ms 55352 KB Output isn't correct
14 Runtime error 2837 ms 93376 KB Execution killed with signal 13
15 Runtime error 308 ms 63028 KB Execution killed with signal 13
16 Runtime error 312 ms 80556 KB Execution killed with signal 13
17 Runtime error 2299 ms 121860 KB Execution killed with signal 13