oj.uz

Submission #929031

# Submission time Handle Problem Language Result Execution time Memory
929031 2024-02-17T13:51:50 Z dosts Regions (IOI09_regions) C++17
75 / 100
 3959 ms 131072 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 = 151,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 50 ms 126032 KB Output is correct
2 Correct 16 ms 126040 KB Output is correct
3 Correct 15 ms 126236 KB Output is correct
4 Correct 18 ms 126296 KB Output is correct
5 Correct 18 ms 126268 KB Output is correct
6 Correct 24 ms 126320 KB Output is correct
7 Correct 30 ms 126296 KB Output is correct
8 Correct 31 ms 126356 KB Output is correct
9 Correct 38 ms 126808 KB Output is correct
10 Correct 65 ms 126652 KB Output is correct
11 Correct 81 ms 126924 KB Output is correct
12 Correct 84 ms 127432 KB Output is correct
13 Correct 120 ms 126964 KB Output is correct
14 Correct 142 ms 127496 KB Output is correct
15 Correct 139 ms 130528 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 130212 KB Output is correct
2 Correct 500 ms 128804 KB Output is correct
3 Correct 1265 ms 130128 KB Output is correct
4 Correct 151 ms 127712 KB Output is correct
5 Correct 240 ms 129628 KB Output is correct
6 Correct 314 ms 128832 KB Output is correct
7 Correct 486 ms 129756 KB Output is correct
8 Correct 691 ms 129592 KB Output is correct
9 Correct 1297 ms 130904 KB Output is correct
10 Runtime error 82 ms 131072 KB Execution killed with signal 9
11 Correct 3959 ms 130424 KB Output is correct
12 Runtime error 81 ms 131072 KB Execution killed with signal 9
13 Correct 1273 ms 130316 KB Output is correct
14 Correct 1426 ms 129860 KB Output is correct
15 Runtime error 77 ms 131072 KB Execution killed with signal 9
16 Runtime error 67 ms 131072 KB Execution killed with signal 9
17 Runtime error 70 ms 131072 KB Execution killed with signal 9