oj.uz

Submission #593358

# Submission time Handle Problem Language Result Execution time Memory
593358 2022-07-10T23:49:55 Z Bench0310 Regions (IOI09_regions) C++17
0 / 100
 2447 ms 82600 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=200005;
const int R=25005;
const int S=105;
const int BIG=N/S;
vector<int> v[N];
int h[N];
vector<int> region[R];
int all[R];
int tcnt=0;
int tin[N];
int tout[N];
vector<int> down[R];
vector<array<int,2>> up[R];
int bigres[BIG][BIG];
vector<int> big;
int bigid[R];
int cnt[R];
int bigcnt=0;

void add_up(int r,int t,int d)
{
    up[r].push_back({t,up[r].back()[1]+d});
}

void dfs(int a)
{
    tin[a]=tcnt++;
    down[h[a]].push_back(tin[a]);
    add_up(h[a],tin[a],1);
    if(bigid[h[a]]!=-1)
    {
        for(int r:big) bigres[bigid[r]][bigid[h[a]]]+=cnt[r];
    }
    cnt[h[a]]++;
    for(int to:v[a]) dfs(to);
    tout[a]=tcnt-1;
    add_up(h[a],tout[a],-1);
    cnt[h[a]]--;
}

int qdown(int x,int l,int r)
{
    return upper_bound(down[x].begin(),down[x].end(),r)-lower_bound(down[x].begin(),down[x].end(),l);
}

int qup(int x,int t)
{
    auto it=lower_bound(up[x].begin(),up[x].end(),array<int,2>{t+1,0});
    return (*prev(it))[1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,r,q;
    cin >> n >> r >> q;
    for(int i=1;i<=R;i++) up[i].push_back({-1,0});
    for(int i=1;i<=n;i++)
    {
        if(i>=2)
        {
            int p;
            cin >> p;
            v[p].push_back(i);
        }
        cin >> h[i];
        region[h[i]].push_back(i);
        all[h[i]]++;
    }
    for(int i=1;i<=r;i++)
    {
        bigid[i]=-1;
        if(all[i]>=S)
        {
            big.push_back(i);
            bigid[i]=bigcnt++;
        }
    }
    dfs(1);
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        int res=0;
        if(all[a]>=S&&all[b]>=S) res=bigres[bigid[a]][bigid[b]];
        else if(all[a]<S)
        {
            for(int x:region[a]) res+=qdown(b,tin[x],tout[x]);
        }
        else if(all[b]<S)
        {
            for(int x:region[b]) res+=qup(a,tin[x]);
        }
        cout << res << endl;
    }
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 15184 KB Execution killed with signal 6
2 Runtime error 14 ms 15172 KB Execution killed with signal 6
3 Runtime error 13 ms 15216 KB Execution killed with signal 6
4 Runtime error 16 ms 15168 KB Execution killed with signal 6
5 Runtime error 20 ms 15328 KB Execution killed with signal 6
6 Runtime error 30 ms 15416 KB Execution killed with signal 6
7 Runtime error 38 ms 15400 KB Execution killed with signal 6
8 Runtime error 44 ms 15580 KB Execution killed with signal 6
9 Runtime error 58 ms 16840 KB Execution killed with signal 6
10 Runtime error 97 ms 16832 KB Execution killed with signal 6
11 Runtime error 112 ms 17484 KB Execution killed with signal 6
12 Runtime error 154 ms 19228 KB Execution killed with signal 6
13 Runtime error 190 ms 18132 KB Execution killed with signal 6
14 Runtime error 194 ms 21216 KB Execution killed with signal 6
15 Runtime error 197 ms 29044 KB Execution killed with signal 6

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 673 ms 28256 KB Execution killed with signal 6
2 Runtime error 969 ms 24660 KB Execution killed with signal 6
3 Runtime error 1157 ms 34536 KB Execution killed with signal 6
4 Runtime error 279 ms 20728 KB Execution killed with signal 6
5 Runtime error 352 ms 25452 KB Execution killed with signal 6
6 Runtime error 558 ms 24176 KB Execution killed with signal 6
7 Runtime error 799 ms 27884 KB Execution killed with signal 6
8 Runtime error 1055 ms 43636 KB Execution killed with signal 6
9 Runtime error 1848 ms 47464 KB Execution killed with signal 6
10 Runtime error 2214 ms 64880 KB Execution killed with signal 6
11 Runtime error 2432 ms 42148 KB Execution killed with signal 6
12 Runtime error 1507 ms 47928 KB Execution killed with signal 6
13 Runtime error 1795 ms 50472 KB Execution killed with signal 6
14 Runtime error 2090 ms 51556 KB Execution killed with signal 6
15 Runtime error 2447 ms 66176 KB Execution killed with signal 6
16 Runtime error 2435 ms 82600 KB Execution killed with signal 6
17 Runtime error 2310 ms 79248 KB Execution killed with signal 6