oj.uz

Submission #870907

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

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 id[MXN];
int dp[MXN];
int in[MXN], out[MXN];
int mp[MXN/B + 10][25000];
int mp1[MXN/B + 10][25000];
int tim = -1;
int cur = -1;

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[id[cur]][reg[a]] = mp[id[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) mp1[id[cur]][reg[a]]= mp[id[cur]][reg[a]] + 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]));
    }
    int cnt = 0;
    for (int i = 1; i <= r; i++)
    {
        if (idx[i].size() < B) continue; 
        id[i] = cnt++;
    }
    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 (idx[u].size() >= B)
        {
            cout << mp[id[u]][v] << endl;
            continue;
        }
        if (idx[v].size() >= B)
        {
            cout << mp1[id[v]][u] << endl;
        }
        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++;
            }
        }
        cout << ans << endl;
    }
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26968 KB Output is correct
2 Correct 5 ms 26968 KB Output is correct
3 Correct 6 ms 26968 KB Output is correct
4 Correct 7 ms 26968 KB Output is correct
5 Correct 9 ms 26968 KB Output is correct
6 Correct 14 ms 27224 KB Output is correct
7 Correct 19 ms 27096 KB Output is correct
8 Correct 20 ms 27224 KB Output is correct
9 Correct 32 ms 27736 KB Output is correct
10 Correct 47 ms 27992 KB Output is correct
11 Correct 71 ms 28416 KB Output is correct
12 Correct 80 ms 29560 KB Output is correct
13 Correct 91 ms 29536 KB Output is correct
14 Correct 125 ms 30692 KB Output is correct
15 Correct 146 ms 33668 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 39996 KB Execution killed with signal 13
2 Runtime error 55 ms 38568 KB Execution killed with signal 13
3 Runtime error 74 ms 44648 KB Execution killed with signal 13
4 Correct 165 ms 30104 KB Output is correct
5 Correct 205 ms 31816 KB Output is correct
6 Correct 441 ms 31848 KB Output is correct
7 Correct 639 ms 34152 KB Output is correct
8 Correct 594 ms 42032 KB Output is correct
9 Correct 1031 ms 46664 KB Output is correct
10 Correct 1388 ms 50556 KB Output is correct
11 Correct 1595 ms 47148 KB Output is correct
12 Runtime error 510 ms 52704 KB Execution killed with signal 13
13 Execution timed out 520 ms 53196 KB Time limit exceeded (wall clock)
14 Execution timed out 725 ms 53428 KB Time limit exceeded (wall clock)
15 Execution timed out 589 ms 59368 KB Time limit exceeded (wall clock)
16 Execution timed out 492 ms 67412 KB Time limit exceeded (wall clock)
17 Runtime error 155 ms 66816 KB Execution killed with signal 13