oj.uz

Submission #718199

# Submission time Handle Problem Language Result Execution time Memory
718199 2023-04-03T15:39:11 Z bLIC Regions (IOI09_regions) C++17
21 / 100
 4378 ms 33188 KB 
/**
 *  Author: Anil Byar
**/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// template<class T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back

// Source: https://codeforces.com/blog/entry/68809
// { start
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// } end


typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 1e9+7;
const ll MOD9 = 998244353;
const ll INFLL = 1e18+5;
const int INF = 1e9;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;}
ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);}

template<class T>
istream& operator>>(istream&in, vector<T>&v){
    for (T& x:v) in>>x;
    return in;
}
template<class T>
ostream& operator<<(ostream&out, vector<T>&v){
    for (T& x:v) out<<x<<' ';
    cout<<'\n';
    return out;
}
// use ?: with brackets (?:)
// check for overflow
// think about dp


const int maxN = 2e4+5;
const int maxK = 2505;
int B = 447;
int n, r, q;
vvi adj;
vi regof;
vvi timing;
vi st, en;
vvi reg;
vector<bool> heavy;
unordered_map<int, int> cont;
unordered_map<int, int> ansforheavy[maxK];
int tim, hvy;


void dfs(int node){
    st[node] = tim++;
    if (heavy[regof[node]]){
        cont[regof[node]]++;
    }
    timing[regof[node]].push_back(st[node]);
    for (int x:adj[node]){
        for (auto y:cont){
            ansforheavy[regof[x]][y.ft] += y.sd;
        }
        dfs(x);
    }
    en[node] = tim;
    if (heavy[regof[node]]){
        cont[regof[node]]--;
    }
}

ll query(int r1, int r2){
    if (heavy[r1]) return ansforheavy[regof[r2]][regof[r1]];
    else {
        ll ans = 0;
        for (int x:reg[r1]){
            ans += lower_bound(all(timing[r2]), en[x])-upper_bound(all(timing[r2]), st[x]);
        }
        return ans;
    }
}

void solve(){
    cin>>n>>r>>q;
    // B = sqrt(n);
    adj.resize(n+1);
    regof.resize(n+1);
    timing.resize(r+1);
    st.resize(n+1);
    en.resize(n+1);
    reg.resize(r+1);
    heavy.resize(r+1);
    cin>>regof[1];
    reg[regof[1]].push_back(1);
    for (int i = 2;i<=n;i++){
        int p;
        cin>>p>>regof[i];
        reg[regof[i]].push_back(i);
        // if (sz(reg[regof[i]])>B+1) reg[regof[i]].pop_back();
        adj[p].push_back(i);
    }
    
    for (int i = 1;i<=r;i++){
        if (sz(reg[i])>B){
            heavy[i] = true;
        }
    }
    dfs(1);

    while(q--){
        int r1, r2;
        cin>>r1>>r2;
        cout<<query(r1, r2)<<endl;
    }
}

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);


// #ifndef ONLINE_JUDGE
//     freopen("input.in", "r", stdin);
//     freopen("output.out", "w", stdout);
//     freopen("debug.dbg", "w", stderr);
//     int tt = clock();
// #endif

    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        cout<<'\n';
    }
// #ifndef ONLINE_JUDGE
//     cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
//     tt = clock();
// #endif
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:184:14: warning: unused variable 'i' [-Wunused-variable]
  184 |     int t=1, i = 1;
      |              ^

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 7 ms 464 KB Output is correct
6 Correct 17 ms 592 KB Output is correct
7 Correct 26 ms 464 KB Output is correct
8 Correct 31 ms 592 KB Output is correct
9 Correct 58 ms 1360 KB Output is correct
10 Correct 91 ms 1232 KB Output is correct
11 Correct 124 ms 1616 KB Output is correct
12 Runtime error 151 ms 2512 KB Execution killed with signal 13
13 Runtime error 167 ms 2000 KB Execution killed with signal 13
14 Runtime error 314 ms 2732 KB Execution killed with signal 13
15 Runtime error 254 ms 8128 KB Execution killed with signal 13

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 2120 ms 7936 KB Execution killed with signal 13
2 Incorrect 1921 ms 6072 KB Output isn't correct
3 Runtime error 3223 ms 11308 KB Execution killed with signal 13
4 Correct 207 ms 3016 KB Output is correct
5 Correct 366 ms 6424 KB Output is correct
6 Runtime error 35 ms 8428 KB Execution killed with signal 11
7 Runtime error 50 ms 11408 KB Execution killed with signal 11
8 Runtime error 67 ms 16584 KB Execution killed with signal 11
9 Runtime error 2719 ms 15292 KB Execution killed with signal 13
10 Runtime error 119 ms 28972 KB Execution killed with signal 11
11 Runtime error 4378 ms 15816 KB Execution killed with signal 13
12 Runtime error 135 ms 30068 KB Execution killed with signal 11
13 Runtime error 132 ms 28932 KB Execution killed with signal 11
14 Runtime error 151 ms 30112 KB Execution killed with signal 11
15 Runtime error 172 ms 33188 KB Execution killed with signal 11
16 Runtime error 145 ms 32896 KB Execution killed with signal 11
17 Runtime error 140 ms 32424 KB Execution killed with signal 11