oj.uz

Submission #899925

# Submission time Handle Problem Language Result Execution time Memory
899925 2024-01-07T10:17:09 Z ninjamayank Regions (IOI09_regions) C++17
90 / 100
 3734 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 >= 600){
            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 <= 600){
            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 56 ms 110928 KB Output is correct
2 Correct 48 ms 110924 KB Output is correct
3 Correct 58 ms 110932 KB Output is correct
4 Correct 49 ms 110932 KB Output is correct
5 Correct 52 ms 110932 KB Output is correct
6 Correct 56 ms 110936 KB Output is correct
7 Correct 66 ms 110884 KB Output is correct
8 Correct 63 ms 110932 KB Output is correct
9 Correct 75 ms 111312 KB Output is correct
10 Correct 95 ms 111368 KB Output is correct
11 Correct 119 ms 111656 KB Output is correct
12 Correct 136 ms 112124 KB Output is correct
13 Correct 154 ms 112372 KB Output is correct
14 Correct 221 ms 112680 KB Output is correct
15 Correct 254 ms 114996 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1613 ms 115760 KB Output is correct
2 Correct 1782 ms 115600 KB Output is correct
3 Correct 2333 ms 117704 KB Output is correct
4 Correct 214 ms 112748 KB Output is correct
5 Correct 301 ms 114000 KB Output is correct
6 Correct 1095 ms 114032 KB Output is correct
7 Correct 1277 ms 115264 KB Output is correct
8 Correct 975 ms 119440 KB Output is correct
9 Correct 1742 ms 120852 KB Output is correct
10 Correct 3734 ms 124592 KB Output is correct
11 Correct 3352 ms 123500 KB Output is correct
12 Correct 1113 ms 121272 KB Output is correct
13 Correct 1626 ms 122408 KB Output is correct
14 Correct 1702 ms 122876 KB Output is correct
15 Correct 2573 ms 126436 KB Output is correct
16 Runtime error 161 ms 131072 KB Execution killed with signal 9
17 Runtime error 158 ms 131072 KB Execution killed with signal 9