oj.uz

Submission #914241

# Submission time Handle Problem Language Result Execution time Memory
914241 2024-01-21T12:19:56 Z VMaksimoski008 Regions (IOI09_regions) C++14
80 / 100
 8000 ms 28052 KB 
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
 
using namespace std;
using pii = pair<int, int>;
 
const int maxn = 2e5 + 5;
 
int n, r, q, in[maxn], out[maxn], timer = 0, B = 500, curr = 0, dp[210][25005];
short home[maxn], id[maxn];
vector<vector<int> > graph;
vector<vector<pii> > by_home;
 
void dfs(int u) {
    in[u] = timer++;
 
    for(int &v : graph[u])
        dfs(v);
 
    out[u] = timer;
}
 
void dfs2(int u, int R, int cnt) {
    if(home[u] == R) cnt++;
    dp[id[R]][home[u]] += cnt;
    for(int &v : graph[u]) dfs2(v, R, cnt);
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> r >> q;
    graph.resize(n+1);
    by_home.resize(r+1);
    
    cin >> home[1];
 
    for(int i=2; i<=n; i++) {
        int p;
        cin >> p >> home[i];
        graph[p].push_back(i);
    }
 
    dfs(1);
 
    for(int i=1; i<=n; i++)
        by_home[home[i]].push_back({ in[i], out[i] });

    for(int i=1; i<=r; i++) {
        sort(all(by_home[i]));
        if(sz(by_home[i]) <= B) continue;
        id[i] = curr;
        dfs2(1, i, 0);
        curr++;
    }
 
    while(q--) {
        int r1, r2, ans = 0;
        cin >> r1 >> r2;
 
        for(pii &u : by_home[r1]) {
            //cout << u.first << " " << u.second << '\n';
            int l=0, r=sz(by_home[r2])-1;
            int p1 = 1e9;
 
            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first > u.first) p1 = mid, r = mid - 1;
                else l = mid + 1;
            }
 
            if(p1 == 1e9) continue;
            
            l=p1, r=sz(by_home[r2])-1;
            int p2 = 1e9;
 
            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first < u.second) p2 = mid, l = mid + 1;
                else r = mid - 1;
            }
 
            if(p2 == 1e9) continue;
 
            ans += (p2 - p1 + 1);
        }
 
        cout << ans << endl;
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 3 ms 2552 KB Output is correct
6 Correct 10 ms 2392 KB Output is correct
7 Correct 14 ms 2392 KB Output is correct
8 Correct 16 ms 2648 KB Output is correct
9 Correct 26 ms 2904 KB Output is correct
10 Correct 45 ms 3160 KB Output is correct
11 Correct 60 ms 3416 KB Output is correct
12 Correct 84 ms 3996 KB Output is correct
13 Correct 95 ms 3928 KB Output is correct
14 Correct 147 ms 4764 KB Output is correct
15 Correct 178 ms 6848 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8079 ms 8596 KB Time limit exceeded
2 Execution timed out 8055 ms 7588 KB Time limit exceeded
3 Execution timed out 8066 ms 10676 KB Time limit exceeded
4 Correct 132 ms 4800 KB Output is correct
5 Correct 209 ms 6060 KB Output is correct
6 Correct 758 ms 6424 KB Output is correct
7 Correct 964 ms 7872 KB Output is correct
8 Correct 798 ms 12432 KB Output is correct
9 Correct 1313 ms 14704 KB Output is correct
10 Correct 3015 ms 18688 KB Output is correct
11 Correct 2284 ms 15696 KB Output is correct
12 Correct 2425 ms 17004 KB Output is correct
13 Correct 2981 ms 17220 KB Output is correct
14 Correct 3872 ms 19232 KB Output is correct
15 Correct 4608 ms 21268 KB Output is correct
16 Correct 5531 ms 26648 KB Output is correct
17 Execution timed out 8050 ms 28052 KB Time limit exceeded