oj.uz

Submission #899912

# Submission time Handle Problem Language Result Execution time Memory
899912 2024-01-07T09:59:52 Z ninjamayank Regions (IOI09_regions) C++17
45 / 100
 3529 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 110808 KB Output is correct
2 Correct 49 ms 110800 KB Output is correct
3 Correct 52 ms 110800 KB Output is correct
4 Correct 59 ms 110928 KB Output is correct
5 Correct 51 ms 110928 KB Output is correct
6 Correct 61 ms 110880 KB Output is correct
7 Correct 62 ms 110928 KB Output is correct
8 Correct 68 ms 110936 KB Output is correct
9 Correct 78 ms 111356 KB Output is correct
10 Correct 102 ms 111464 KB Output is correct
11 Correct 122 ms 111660 KB Output is correct
12 Correct 143 ms 112140 KB Output is correct
13 Correct 147 ms 112396 KB Output is correct
14 Correct 233 ms 112700 KB Output is correct
15 Correct 252 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 86 ms 131072 KB Execution killed with signal 9
3 Runtime error 82 ms 131072 KB Execution killed with signal 9
4 Correct 190 ms 112768 KB Output is correct
5 Correct 272 ms 114020 KB Output is correct
6 Incorrect 881 ms 114048 KB Output isn't correct
7 Correct 1308 ms 115292 KB Output is correct
8 Incorrect 1052 ms 119460 KB Output isn't correct
9 Correct 1759 ms 120876 KB Output is correct
10 Correct 3529 ms 124604 KB Output is correct
11 Correct 3487 ms 123488 KB Output is correct
12 Runtime error 124 ms 131072 KB Execution killed with signal 9
13 Runtime error 110 ms 131072 KB Execution killed with signal 9
14 Runtime error 119 ms 131072 KB Execution killed with signal 9
15 Runtime error 117 ms 131072 KB Execution killed with signal 9
16 Runtime error 118 ms 131072 KB Execution killed with signal 9
17 Runtime error 121 ms 131072 KB Execution killed with signal 9