oj.uz

Submission #870906

# Submission time Handle Problem Language Result Execution time Memory
870906 2023-11-09T12:43:07 Z aykhn Regions (IOI09_regions) C++17
45 / 100
 1645 ms 73304 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 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 22872 KB Output is correct
2 Correct 4 ms 22872 KB Output is correct
3 Correct 7 ms 22872 KB Output is correct
4 Correct 7 ms 22960 KB Output is correct
5 Correct 9 ms 22884 KB Output is correct
6 Correct 11 ms 23124 KB Output is correct
7 Correct 16 ms 23128 KB Output is correct
8 Correct 20 ms 23128 KB Output is correct
9 Correct 31 ms 23640 KB Output is correct
10 Correct 45 ms 23896 KB Output is correct
11 Correct 67 ms 24484 KB Output is correct
12 Correct 77 ms 25384 KB Output is correct
13 Correct 99 ms 25576 KB Output is correct
14 Correct 110 ms 26828 KB Output is correct
15 Correct 150 ms 31948 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 42368 KB Execution killed with signal 13
2 Runtime error 75 ms 42532 KB Execution killed with signal 13
3 Runtime error 80 ms 42864 KB Execution killed with signal 13
4 Correct 163 ms 26236 KB Output is correct
5 Correct 229 ms 29968 KB Output is correct
6 Runtime error 71 ms 40636 KB Execution killed with signal 13
7 Correct 647 ms 32276 KB Output is correct
8 Runtime error 71 ms 46652 KB Execution killed with signal 13
9 Correct 1032 ms 42732 KB Output is correct
10 Correct 1424 ms 46824 KB Output is correct
11 Correct 1645 ms 43488 KB Output is correct
12 Runtime error 554 ms 50740 KB Execution killed with signal 13
13 Execution timed out 539 ms 51292 KB Time limit exceeded (wall clock)
14 Runtime error 641 ms 58172 KB Execution killed with signal 13
15 Execution timed out 583 ms 57704 KB Time limit exceeded (wall clock)
16 Execution timed out 477 ms 65520 KB Time limit exceeded (wall clock)
17 Runtime error 297 ms 73304 KB Execution killed with signal 13