oj.uz

Submission #929027

# Submission time Handle Problem Language Result Execution time Memory
929027 2024-02-17T13:44:23 Z dosts Regions (IOI09_regions) C++17
6 / 100
 90 ms 62620 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) {
            //Az geçiyor, binary search
            int sm = 0;
            for (auto it : posses[r1]) {
                int l=  tin[it];
                int r = tout[it];
                //l ve r arasında kaç tane r2 var
                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();
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:73:34: warning: array subscript 151 is above array bounds of 'int [151][200001]' [-Warray-bounds]
   73 |         else cout << prec[ind[r1]][r2] << endl;
      |                      ~~~~~~~~~~~~^
regions.cpp:15:5: note: while referencing 'prec'
   15 | int prec[B][N];
      |     ^~~~

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 4 ms 9280 KB Output is correct
3 Correct 3 ms 9280 KB Output is correct
4 Correct 5 ms 9276 KB Output is correct
5 Correct 6 ms 9312 KB Output is correct
6 Runtime error 12 ms 18536 KB Execution killed with signal 11
7 Correct 17 ms 9352 KB Output is correct
8 Runtime error 12 ms 18704 KB Execution killed with signal 11
9 Runtime error 13 ms 19544 KB Execution killed with signal 11
10 Runtime error 16 ms 19148 KB Execution killed with signal 11
11 Runtime error 14 ms 19752 KB Execution killed with signal 11
12 Runtime error 16 ms 20732 KB Execution killed with signal 11
13 Runtime error 18 ms 19756 KB Execution killed with signal 11
14 Runtime error 18 ms 20824 KB Execution killed with signal 11
15 Runtime error 25 ms 27200 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 26312 KB Execution killed with signal 11
2 Runtime error 47 ms 23612 KB Execution killed with signal 11
3 Runtime error 32 ms 30384 KB Execution killed with signal 11
4 Runtime error 19 ms 21524 KB Execution killed with signal 11
5 Runtime error 25 ms 25224 KB Execution killed with signal 11
6 Runtime error 27 ms 23652 KB Execution killed with signal 11
7 Runtime error 30 ms 25504 KB Execution killed with signal 11
8 Runtime error 43 ms 36984 KB Execution killed with signal 11
9 Runtime error 66 ms 35388 KB Execution killed with signal 11
10 Runtime error 63 ms 47892 KB Execution killed with signal 11
11 Runtime error 68 ms 34208 KB Execution killed with signal 11
12 Runtime error 86 ms 36776 KB Execution killed with signal 11
13 Runtime error 68 ms 37444 KB Execution killed with signal 11
14 Runtime error 72 ms 36828 KB Execution killed with signal 11
15 Runtime error 90 ms 47828 KB Execution killed with signal 11
16 Runtime error 79 ms 62620 KB Execution killed with signal 11
17 Runtime error 77 ms 59148 KB Execution killed with signal 11