oj.uz

Submission #898960

# Submission time Handle Problem Language Result Execution time Memory
898960 2024-01-05T10:14:56 Z a_l_i_r_e_z_a Regions (IOI09_regions) C++14
100 / 100
 3148 ms 33848 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 = 330 + 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 = 600;
    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 3 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 10 ms 12888 KB Output is correct
7 Correct 14 ms 12888 KB Output is correct
8 Correct 16 ms 12888 KB Output is correct
9 Correct 27 ms 13400 KB Output is correct
10 Correct 46 ms 13380 KB Output is correct
11 Correct 62 ms 13420 KB Output is correct
12 Correct 78 ms 13912 KB Output is correct
13 Correct 91 ms 13540 KB Output is correct
14 Correct 152 ms 14168 KB Output is correct
15 Correct 194 ms 16724 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1355 ms 18768 KB Output is correct
2 Correct 1500 ms 17564 KB Output is correct
3 Correct 1983 ms 20404 KB Output is correct
4 Correct 145 ms 14136 KB Output is correct
5 Correct 193 ms 15704 KB Output is correct
6 Correct 973 ms 15288 KB Output is correct
7 Correct 1097 ms 15896 KB Output is correct
8 Correct 810 ms 20816 KB Output is correct
9 Correct 1413 ms 20620 KB Output is correct
10 Correct 3148 ms 25308 KB Output is correct
11 Correct 2663 ms 19884 KB Output is correct
12 Correct 842 ms 23176 KB Output is correct
13 Correct 1220 ms 23600 KB Output is correct
14 Correct 1423 ms 25380 KB Output is correct
15 Correct 2172 ms 27732 KB Output is correct
16 Correct 1996 ms 32920 KB Output is correct
17 Correct 2009 ms 33848 KB Output is correct