oj.uz

Submission #914028

# Submission time Handle Problem Language Result Execution time Memory
914028 2024-01-20T19:37:55 Z VMaksimoski008 Regions (IOI09_regions) C++14
95 / 100
 8000 ms 101496 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;
short home[maxn];
vector<vector<int> > graph, dp;
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) {
    dp[home[u]][u]++;

    for(int &v : graph[u]) {
        dfs2(v);
        for(int i=1; i<=r; i++)
            dp[i][u] += dp[i][v];
    }
}

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);
    }

    if(r <= 500) {
        dp.resize(r+1, vector<int>(n+1));
        dfs2(1);

        vector<vector<int> > reg(n+1);
        for(int i=1; i<=n; i++)
            reg[home[i]].push_back(i);

        while(q--) {
            int r1, r2, ans=0;
            cin >> r1 >> r2;
    
            for(int &x : reg[r1])
                ans += dp[r2][x];
    
            cout << ans << '\n';
            cout.flush();
        }

        return 0;
    }

    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]));

    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 << '\n';
        cout.flush();
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 9 ms 1112 KB Output is correct
7 Correct 13 ms 1368 KB Output is correct
8 Correct 16 ms 2136 KB Output is correct
9 Correct 24 ms 6744 KB Output is correct
10 Correct 60 ms 17844 KB Output is correct
11 Correct 71 ms 17704 KB Output is correct
12 Correct 109 ms 37716 KB Output is correct
13 Correct 177 ms 34264 KB Output is correct
14 Correct 122 ms 26588 KB Output is correct
15 Correct 402 ms 43864 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 66904 KB Output is correct
2 Correct 1578 ms 76460 KB Output is correct
3 Correct 1758 ms 101496 KB Output is correct
4 Correct 161 ms 2808 KB Output is correct
5 Correct 230 ms 4340 KB Output is correct
6 Correct 779 ms 4472 KB Output is correct
7 Correct 945 ms 5952 KB Output is correct
8 Correct 699 ms 10476 KB Output is correct
9 Correct 1342 ms 12940 KB Output is correct
10 Correct 2966 ms 17088 KB Output is correct
11 Correct 2387 ms 14036 KB Output is correct
12 Correct 2343 ms 15264 KB Output is correct
13 Correct 2895 ms 15236 KB Output is correct
14 Correct 3598 ms 15352 KB Output is correct
15 Correct 4544 ms 18720 KB Output is correct
16 Correct 5875 ms 21992 KB Output is correct
17 Execution timed out 8003 ms 21192 KB Time limit exceeded