oj.uz

Submission #899920

# Submission time Handle Problem Language Result Execution time Memory
899920 2024-01-07T10:14:06 Z ninjamayank Regions (IOI09_regions) C++17
90 / 100
 3776 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,u,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 47 ms 110928 KB Output is correct
2 Correct 48 ms 110928 KB Output is correct
3 Correct 49 ms 110900 KB Output is correct
4 Correct 52 ms 110928 KB Output is correct
5 Correct 53 ms 110920 KB Output is correct
6 Correct 63 ms 110864 KB Output is correct
7 Correct 64 ms 110888 KB Output is correct
8 Correct 76 ms 110916 KB Output is correct
9 Correct 83 ms 111316 KB Output is correct
10 Correct 99 ms 111360 KB Output is correct
11 Correct 127 ms 111648 KB Output is correct
12 Correct 145 ms 112124 KB Output is correct
13 Correct 186 ms 112372 KB Output is correct
14 Correct 231 ms 112684 KB Output is correct
15 Correct 251 ms 114996 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1581 ms 115760 KB Output is correct
2 Correct 1763 ms 115584 KB Output is correct
3 Correct 2414 ms 117696 KB Output is correct
4 Correct 228 ms 112752 KB Output is correct
5 Correct 312 ms 113996 KB Output is correct
6 Correct 910 ms 114124 KB Output is correct
7 Correct 1351 ms 115272 KB Output is correct
8 Correct 1006 ms 120504 KB Output is correct
9 Correct 1805 ms 120860 KB Output is correct
10 Correct 3776 ms 124580 KB Output is correct
11 Correct 3535 ms 123448 KB Output is correct
12 Correct 1107 ms 121212 KB Output is correct
13 Correct 1699 ms 122408 KB Output is correct
14 Correct 1881 ms 122868 KB Output is correct
15 Correct 2682 ms 126428 KB Output is correct
16 Runtime error 169 ms 131072 KB Execution killed with signal 9
17 Runtime error 175 ms 131072 KB Execution killed with signal 9