oj.uz

Submission #899913

# Submission time Handle Problem Language Result Execution time Memory
899913 2024-01-07T10:01:00 Z ninjamayank Regions (IOI09_regions) C++17
45 / 100
 3425 ms 131072 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define input(x) for(auto &a:x)cin>>a
#define print(x) for(auto &a:x){cout<<a<<' ';}cout<<nline
#define ppcl(x) __builtin_popcountll(x)
#define ppc(x) __builtin_popcount(x)
#define all(x) x.begin(), x.end()
#define ll long long int
#define ld long double
#define pb push_back
#define nline "\n"
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define pii pair<int,int> 
#define fr first
#define sc second 
using namespace std;
using namespace __gnu_pbds;
#define precision(x) fixed << setprecision(x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const ll mod = 1e9 + 7;
const int N = 200001;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n,r,q;
vector<ll> reg(N), id(N), in(N), out(N);
vector<vector<ll>> g(N);
vector<vector<ll>> res(25010), region(25010);
vector<vector<ll>> dp(500,vector<ll>(25010));
ll cnt = 0,timer = 0, counter = 0;

void dfs(ll u, ll p){
    in[u] = timer++;
    res[reg[u]].pb(in[u]);
    region[reg[u]].pb(u);
    for(auto &child : g[u]){
        if(child == p) continue;
        dfs(child,u);
    }
    out[u] = timer++;
}

void sq_dfs(ll u, ll p, ll col){
    if(reg[u] == col){
        cnt++;
    }else{
        dp[id[col]][reg[u]] += cnt;
    }
    for(auto &child : g[u]){
        if(child == p) continue;
        sq_dfs(child,p,col);
    }
    if(reg[u] == col){
        cnt--;
    }
}

void ninjamayank(){
    cin >> n >> r >> q;
    cin >> reg[0];
    for(ll i = 1;i < n;i++){
        ll x;
        cin >> x >> reg[i];
        --x;
        g[x].pb(i);
        g[i].pb(x);
    }
    dfs(0,-1);
    for(ll i = 1;i <= r;i++){
        ll sz = res[i].size();
        if(sz >= 500){
            id[i] = counter++;
            sq_dfs(0,-1,i);
        }
    }
    while(q--){
        ll r1,r2;
        cin >> r1 >> r2;
        ll sz = res[r1].size();
        ll ans = 0;
        if(sz < 500){
            for(ll i = 0;i < sz;i++){
                ans += lower_bound(all(res[r2]),out[region[r1][i]]) - lower_bound(all(res[r2]),in[region[r1][i]]);
            }
        }else{
            ans = dp[id[r1]][r2];
        }
        cout << ans << endl;
    }
}
int main(){
    // #ifndef ONLINE_JUDGE
    //     //for getting input from input1.txt
    //     freopen("input1.txt", "r", stdin);
    //     //for getting output from output1.txt
    //     freopen("output1.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); // remove in problems with online query
    int testcase = 1;
    // cin >> testcase;
    int gtc = 1;
    while(testcase--){
        //cout << "Case #" << gtc << ": ";
        ninjamayank();
        gtc++;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 110924 KB Output is correct
2 Correct 51 ms 110928 KB Output is correct
3 Correct 50 ms 110928 KB Output is correct
4 Correct 52 ms 110928 KB Output is correct
5 Correct 55 ms 110844 KB Output is correct
6 Correct 61 ms 110884 KB Output is correct
7 Correct 65 ms 110908 KB Output is correct
8 Correct 62 ms 110944 KB Output is correct
9 Correct 81 ms 111352 KB Output is correct
10 Correct 95 ms 111392 KB Output is correct
11 Correct 123 ms 111656 KB Output is correct
12 Correct 120 ms 112140 KB Output is correct
13 Correct 142 ms 112396 KB Output is correct
14 Correct 242 ms 112896 KB Output is correct
15 Correct 239 ms 115020 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 131072 KB Execution killed with signal 9
2 Runtime error 79 ms 131072 KB Execution killed with signal 9
3 Runtime error 78 ms 131072 KB Execution killed with signal 9
4 Correct 229 ms 112768 KB Output is correct
5 Correct 289 ms 114016 KB Output is correct
6 Runtime error 72 ms 131072 KB Execution killed with signal 9
7 Correct 1297 ms 115292 KB Output is correct
8 Runtime error 85 ms 131072 KB Execution killed with signal 9
9 Correct 1655 ms 120880 KB Output is correct
10 Correct 3425 ms 124628 KB Output is correct
11 Correct 3360 ms 123700 KB Output is correct
12 Runtime error 114 ms 131072 KB Execution killed with signal 9
13 Runtime error 110 ms 131072 KB Execution killed with signal 9
14 Runtime error 120 ms 131072 KB Execution killed with signal 9
15 Runtime error 107 ms 131072 KB Execution killed with signal 9
16 Runtime error 113 ms 131072 KB Execution killed with signal 9
17 Runtime error 106 ms 131072 KB Execution killed with signal 9