oj.uz

Submission #929028

# Submission time Handle Problem Language Result Execution time Memory
929028 2024-02-17T13:46:44 Z dosts Regions (IOI09_regions) C++17
6 / 100
 89 ms 62588 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][ind[c[node]]]+=cc[i];
} 



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;

    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 {
            assert(ind[r1] < B);
            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
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9048 KB Output is correct
2 Correct 3 ms 9048 KB Output is correct
3 Correct 3 ms 9276 KB Output is correct
4 Correct 4 ms 9280 KB Output is correct
5 Correct 5 ms 9048 KB Output is correct
6 Runtime error 12 ms 18600 KB Execution killed with signal 6
7 Correct 13 ms 9360 KB Output is correct
8 Runtime error 12 ms 18608 KB Execution killed with signal 6
9 Runtime error 15 ms 19536 KB Execution killed with signal 6
10 Runtime error 17 ms 19288 KB Execution killed with signal 6
11 Runtime error 14 ms 19712 KB Execution killed with signal 6
12 Runtime error 16 ms 20728 KB Execution killed with signal 6
13 Runtime error 17 ms 19952 KB Execution killed with signal 6
14 Runtime error 17 ms 21060 KB Execution killed with signal 6
15 Runtime error 22 ms 27008 KB Execution killed with signal 6

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 26332 KB Execution killed with signal 6
2 Runtime error 37 ms 23628 KB Execution killed with signal 6
3 Runtime error 33 ms 30524 KB Execution killed with signal 6
4 Runtime error 19 ms 21272 KB Execution killed with signal 6
5 Runtime error 22 ms 25228 KB Execution killed with signal 6
6 Runtime error 25 ms 23664 KB Execution killed with signal 6
7 Runtime error 30 ms 25432 KB Execution killed with signal 6
8 Runtime error 40 ms 36976 KB Execution killed with signal 6
9 Runtime error 75 ms 35388 KB Execution killed with signal 6
10 Runtime error 71 ms 47884 KB Execution killed with signal 6
11 Runtime error 64 ms 34028 KB Execution killed with signal 6
12 Runtime error 75 ms 36600 KB Execution killed with signal 6
13 Runtime error 67 ms 37452 KB Execution killed with signal 6
14 Runtime error 72 ms 36852 KB Execution killed with signal 6
15 Runtime error 74 ms 47936 KB Execution killed with signal 6
16 Runtime error 80 ms 62588 KB Execution killed with signal 6
17 Runtime error 89 ms 59284 KB Execution killed with signal 6