oj.uz

Submission #898959

# Submission time Handle Problem Language Result Execution time Memory
898959 2024-01-05T10:12:47 Z a_l_i_r_e_z_a Regions (IOI09_regions) C++14
100 / 100
 2582 ms 37360 KB 
// In the name of Allah
// Hope is last to die
// Khodaya khodet komak kon
// Let's go

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

const int maxn = 2e5 + 10, msq = 500 + 10, maxr = 25000 + 10;
const int inf = 1e9 + 7;
int n, q, R, T, cnt, col, cnoma, sq, dp[msq][maxr], noma[maxn];
int in[maxn], out[maxn], reg[maxn];
vector<int> adj[maxn], region[maxr], alo[maxn];

void dfs(int v = 1){
    in[v] = T++;
    region[reg[v]].pb(v);
    alo[reg[v]].pb(in[v]);
    for(auto u: adj[v]) dfs(u);
    out[v] = T;
}

void dfs_dp(int v, int col){
    if(reg[v] == col) cnt++;
    else dp[noma[col]][reg[v]] += cnt;
    for(auto u: adj[v]) dfs_dp(u, col);
    if(reg[v] == col) cnt--;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> R >> q;
    sq = 400;
    cin >> reg[1];
    for(int i = 2; i <= n; i++){
        int p; cin >> p >> reg[i];
        adj[p].pb(i);
    }
    dfs();
    for(int i = 1; i <= R; i++){
        if(sz(region[i]) >= sq){
            noma[i] = ++cnoma;
            dfs_dp(1, i);
        }
    }
    while(q--){
        int reg1, reg2; cin >> reg1 >> reg2;
        if(sz(region[reg1]) <= sq){
            int ans = 0;
            for(auto v: region[reg1]){
                int l = lower_bound(all(alo[reg2]), in[v]) - alo[reg2].begin();
                int r = upper_bound(all(alo[reg2]), out[v] - 1) - alo[reg2].begin();
                ans += r - l;
            }
            cout << ans << endl;
        }
        else cout << dp[noma[reg1]][reg2] << endl;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 12888 KB Output is correct
5 Correct 5 ms 12888 KB Output is correct
6 Correct 11 ms 12888 KB Output is correct
7 Correct 19 ms 12888 KB Output is correct
8 Correct 23 ms 12888 KB Output is correct
9 Correct 23 ms 13400 KB Output is correct
10 Correct 44 ms 13144 KB Output is correct
11 Correct 71 ms 13400 KB Output is correct
12 Correct 76 ms 13912 KB Output is correct
13 Correct 105 ms 13560 KB Output is correct
14 Correct 162 ms 13980 KB Output is correct
15 Correct 174 ms 16472 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1274 ms 20828 KB Output is correct
2 Correct 1521 ms 17572 KB Output is correct
3 Correct 1962 ms 20404 KB Output is correct
4 Correct 139 ms 14136 KB Output is correct
5 Correct 214 ms 15712 KB Output is correct
6 Correct 358 ms 23476 KB Output is correct
7 Correct 925 ms 20048 KB Output is correct
8 Correct 687 ms 33008 KB Output is correct
9 Correct 1448 ms 20620 KB Output is correct
10 Correct 2025 ms 37360 KB Output is correct
11 Correct 2582 ms 19884 KB Output is correct
12 Correct 779 ms 23352 KB Output is correct
13 Correct 1223 ms 23604 KB Output is correct
14 Correct 1387 ms 25376 KB Output is correct
15 Correct 2055 ms 27732 KB Output is correct
16 Correct 2117 ms 33196 KB Output is correct
17 Correct 2015 ms 33828 KB Output is correct