oj.uz

Submission #929032

# Submission time Handle Problem Language Result Execution time Memory
929032 2024-02-17T13:52:41 Z dosts Regions (IOI09_regions) C++17
100 / 100
 3976 ms 127676 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int N = 2e5+1,MOD = 998244353,B = 125,inf  = 2e9,R = 25001;

vi c(N),edges[N],tin(N),tout(N);
vi occtin[R],ind(R);
int prec[B][N];
int timer = 1;

vi cc(B+1,0);
void dfs(int node,int p) {
    tin[node] = timer++;
    occtin[c[node]].push_back(tin[node]);
    for (auto it : edges[node]) if (it != p) dfs(it,node);
    tout[node] = timer-1;
}

void dfs2(int node,int p) {
    if (ind[c[node]] < B) cc[ind[c[node]]]++;
    for (int i=1;i<B;i++) prec[i][c[node]]+=cc[i];
    for (auto it : edges[node]) if (it != p) dfs2(it,node);
    if (ind[c[node]] < B) cc[ind[c[node]]]--;
} 



void solve() {
    int n,r,q;
    cin >> n >> r >> q;
    cin >> c[1];
    vi occ(r+1,0);
    vi posses[r+1];
    occ[c[1]] = 1;
    posses[c[1]].push_back(1);
    for (int i=2;i<=n;i++) {
        int p;
        cin >> p >> c[i];
        edges[p].push_back(i);
        occ[c[i]]++;
        posses[c[i]].push_back(i);
    } 
    dfs(1,1);
    for (int i=1;i<=r;i++) sort(all(occtin[i])); 
    vi cols(r+1);
    for (int i=1;i<=r;i++) cols[i] = i;
    sort(cols.begin()+1,cols.end(),[&](int x,int y){
        return occ[x] > occ[y];
    });
    for (int i=1;i<=r;i++) ind[cols[i]] = i;
    dfs2(1,1);
    while (q--) {
        int r1,r2;
        cin >> r1 >> r2;
        if (ind[r1] >= B) {
            int sm = 0;
            for (auto it : posses[r1]) {
                int l=  tin[it];
                int r = tout[it];
                auto it1 = upper_bound(all(occtin[r2]),r);
                auto it2 = upper_bound(all(occtin[r2]),l-1);
                sm+=it1-it2;
            } 
            cout << sm << endl;
        }
        else {
            cout << prec[ind[r1]][r2] << endl;
        }
        fflush(stdout);
    }
}           
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif

    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 105816 KB Output is correct
2 Correct 13 ms 106068 KB Output is correct
3 Correct 14 ms 105888 KB Output is correct
4 Correct 14 ms 105892 KB Output is correct
5 Correct 15 ms 105908 KB Output is correct
6 Correct 20 ms 105964 KB Output is correct
7 Correct 27 ms 105960 KB Output is correct
8 Correct 25 ms 105980 KB Output is correct
9 Correct 35 ms 106328 KB Output is correct
10 Correct 56 ms 106320 KB Output is correct
11 Correct 80 ms 106584 KB Output is correct
12 Correct 95 ms 107076 KB Output is correct
13 Correct 121 ms 106620 KB Output is correct
14 Correct 137 ms 107140 KB Output is correct
15 Correct 149 ms 110180 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 109860 KB Output is correct
2 Correct 734 ms 108444 KB Output is correct
3 Correct 1489 ms 111812 KB Output is correct
4 Correct 163 ms 107388 KB Output is correct
5 Correct 205 ms 109280 KB Output is correct
6 Correct 315 ms 108476 KB Output is correct
7 Correct 515 ms 109588 KB Output is correct
8 Correct 663 ms 115044 KB Output is correct
9 Correct 1306 ms 114328 KB Output is correct
10 Correct 1984 ms 120440 KB Output is correct
11 Correct 3976 ms 113660 KB Output is correct
12 Correct 1039 ms 114940 KB Output is correct
13 Correct 1445 ms 115328 KB Output is correct
14 Correct 1423 ms 114992 KB Output is correct
15 Correct 2101 ms 120392 KB Output is correct
16 Correct 1871 ms 127676 KB Output is correct
17 Correct 1870 ms 125940 KB Output is correct