oj.uz

Submission #899916

# Submission time Handle Problem Language Result Execution time Memory
899916 2024-01-07T10:10:18 Z ninjamayank Regions (IOI09_regions) C++17
45 / 100
 3754 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 48 ms 110928 KB Output is correct
2 Correct 48 ms 110932 KB Output is correct
3 Correct 50 ms 110928 KB Output is correct
4 Correct 53 ms 110920 KB Output is correct
5 Correct 58 ms 110856 KB Output is correct
6 Correct 60 ms 110928 KB Output is correct
7 Correct 68 ms 110880 KB Output is correct
8 Correct 66 ms 110928 KB Output is correct
9 Correct 79 ms 111312 KB Output is correct
10 Correct 101 ms 111364 KB Output is correct
11 Correct 131 ms 111704 KB Output is correct
12 Correct 136 ms 112116 KB Output is correct
13 Correct 168 ms 112360 KB Output is correct
14 Correct 243 ms 112688 KB Output is correct
15 Correct 246 ms 115000 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 131072 KB Execution killed with signal 9
2 Runtime error 96 ms 131072 KB Execution killed with signal 9
3 Runtime error 100 ms 131072 KB Execution killed with signal 9
4 Correct 257 ms 112744 KB Output is correct
5 Correct 289 ms 114000 KB Output is correct
6 Runtime error 87 ms 131072 KB Execution killed with signal 9
7 Correct 1418 ms 115272 KB Output is correct
8 Runtime error 108 ms 131072 KB Execution killed with signal 9
9 Correct 1799 ms 121004 KB Output is correct
10 Correct 3754 ms 124632 KB Output is correct
11 Correct 3595 ms 123476 KB Output is correct
12 Runtime error 164 ms 131072 KB Execution killed with signal 9
13 Runtime error 178 ms 131072 KB Execution killed with signal 9
14 Runtime error 172 ms 131072 KB Execution killed with signal 9
15 Runtime error 161 ms 131072 KB Execution killed with signal 9
16 Runtime error 176 ms 131072 KB Execution killed with signal 9
17 Runtime error 158 ms 131072 KB Execution killed with signal 9