oj.uz

Submission #469336

# Submission time Handle Problem Language Result Execution time Memory
469336 2021-08-31T13:46:55 Z MohamedFaresNebili Regions (IOI09_regions) C++14
10 / 100
 1991 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using ld  = long double;
using db  = double;
using ii  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;

#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

ld dist(ld x, ld y, ld a, ld b)    { return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
ll gcd(ll a , ll b){ return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b){ return (a * b) / gcd(a , b);}
ll fact(ll n) { return n > 1?(n * fact(n-1)):1;}

const ll MOD = 1000*1000*1000+7;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const long long INF = 1e18;
/// const int nx[4] = {0, 0, -1, 1}, ny[4] = {1, -1, 0, 0};
const int nx[8] = {2, 2, 1, -1, -2, -2, 1, -1};
const int ny[8] = {1, -1, 2, 2, -1, 1, -2, -2};

ll n, r, q, home[200005], st[524][200005];
vector<ll>adj[200005]; ll ans[1000][1000];
ll in[200005], out[200005], timer=0;
void update(ll v, ll l, ll r, ll ind, ll h) {
    if(l==r) { st[h][v]++; return; }
    ll mid=(l+r)/2;
    if(ind<=mid) update(v*2, l, mid, ind, h);
    else update(v*2+1, mid+1, r, ind, h);
    st[h][v]=st[h][v*2]+st[h][v*2+1];
}
void dfs(ll v, ll p) {
    in[v]=timer++;
    for(auto u:adj[v]) {
        if(u==p) continue;
        dfs(u, v);
    }
    out[v]=timer-1;
}
ll query(ll v, ll l, ll r, ll lo, ll hi, ll h) {
    if(l>hi||r<lo) return 0;
    if(l>=lo&&r<=hi) return st[h][v];
    return query(v*2, l, (l+r)/2, lo, hi, h)+query(v*2+1, (l+r)/2+1, r, lo, hi, h);
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    cin>>n>>r>>q; cin>>home[1];
    for(ll l=2;l<=n;l++) {
        ll a; cin>>a; cin>>home[l]; adj[a].pb(l);
    }
    dfs(1, 0); ll s=n;
    while(__builtin_popcount(s)!=1) s++;
    for(ll l=1;l<=n;l++) update(1, 1, s, in[l], home[l]);
    for(ll l=1;l<=n;l++) {
        for(ll i=1;i<=r;i++) {
            if(home[l]==i) continue;
            ans[home[l]][i]+=query(1, 1, s, in[l], out[l], i);
        }
    }
    while(q--) {
        ll r1, r2; cin>>r1>>r2;
        cout<<ans[r1][r2]<<'\n'<<flush;
    }
    return 0;
}

Subtask #1
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5064 KB Output isn't correct
2 Correct 3 ms 5064 KB Output is correct
3 Incorrect 6 ms 5192 KB Output isn't correct
4 Incorrect 8 ms 5576 KB Output isn't correct
5 Correct 15 ms 5832 KB Output is correct
6 Correct 48 ms 11136 KB Output is correct
7 Correct 65 ms 10824 KB Output is correct
8 Correct 96 ms 13372 KB Output is correct
9 Correct 464 ms 33188 KB Output is correct
10 Correct 1043 ms 70160 KB Output is correct
11 Correct 1166 ms 68776 KB Output is correct
12 Runtime error 128 ms 131076 KB Execution killed with signal 9
13 Correct 1991 ms 126796 KB Output is correct
14 Correct 1601 ms 100856 KB Output is correct
15 Runtime error 87 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 131076 KB Execution killed with signal 9
2 Runtime error 97 ms 131076 KB Execution killed with signal 9
3 Runtime error 95 ms 131076 KB Execution killed with signal 9
4 Runtime error 53 ms 11916 KB Execution killed with signal 11
5 Runtime error 55 ms 13640 KB Execution killed with signal 11
6 Runtime error 60 ms 13500 KB Execution killed with signal 11
7 Runtime error 67 ms 14724 KB Execution killed with signal 11
8 Runtime error 88 ms 20064 KB Execution killed with signal 11
9 Runtime error 95 ms 21088 KB Execution killed with signal 11
10 Runtime error 95 ms 26048 KB Execution killed with signal 11
11 Runtime error 121 ms 21948 KB Execution killed with signal 11
12 Runtime error 120 ms 23608 KB Execution killed with signal 11
13 Runtime error 112 ms 23676 KB Execution killed with signal 11
14 Runtime error 115 ms 23380 KB Execution killed with signal 11
15 Runtime error 103 ms 27200 KB Execution killed with signal 11
16 Runtime error 109 ms 32960 KB Execution killed with signal 11
17 Runtime error 116 ms 31804 KB Execution killed with signal 11