oj.uz

Submission #914029

# Submission time Handle Problem Language Result Execution time Memory
914029 2024-01-20T19:45:08 Z VMaksimoski008 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 101340 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, i, r1, r2, ans, lp, rp, mid;
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(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(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(i=1; i<=n; i++)
            reg[home[i]].push_back(i);

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

        return 0;
    }

    dfs(1);

    for(i=1; i<=n; i++)
        by_home[home[i]].push_back({ in[i], out[i] });
    for(i=1; i<=r; i++)
        sort(all(by_home[i]));

    while(q--) {
        ans = 0;
        cin >> r1 >> r2;

        for(pii &u : by_home[r1]) {
            lp=0, rp=sz(by_home[r2])-1;
            int p1 = 1e9;

            while(lp <= rp) {
                mid = (lp + rp) / 2;
                if(by_home[r2][mid].first > u.first) p1 = mid, rp = mid - 1;
                else lp = mid + 1;
            }

            if(p1 == 1e9) continue;
            
            lp=p1, rp=sz(by_home[r2])-1;
            int p2 = 1e9;

            while(lp <= rp) {
                mid = (lp + rp) / 2;
                if(by_home[r2][mid].first < u.second) p2 = mid, lp = mid + 1;
                else rp = 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 9 ms 1368 KB Output is correct
7 Correct 15 ms 1368 KB Output is correct
8 Correct 14 ms 2136 KB Output is correct
9 Correct 34 ms 6744 KB Output is correct
10 Correct 67 ms 18004 KB Output is correct
11 Correct 77 ms 17712 KB Output is correct
12 Correct 119 ms 37720 KB Output is correct
13 Correct 194 ms 34260 KB Output is correct
14 Correct 126 ms 26596 KB Output is correct
15 Correct 225 ms 43868 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1064 ms 66912 KB Output is correct
2 Correct 1424 ms 76500 KB Output is correct
3 Correct 1662 ms 101340 KB Output is correct
4 Correct 141 ms 2804 KB Output is correct
5 Correct 198 ms 4184 KB Output is correct
6 Correct 711 ms 4472 KB Output is correct
7 Correct 941 ms 6120 KB Output is correct
8 Correct 755 ms 10476 KB Output is correct
9 Correct 1283 ms 12932 KB Output is correct
10 Correct 3027 ms 16988 KB Output is correct
11 Correct 2294 ms 14036 KB Output is correct
12 Correct 2460 ms 15260 KB Output is correct
13 Correct 3119 ms 15220 KB Output is correct
14 Correct 3657 ms 15528 KB Output is correct
15 Correct 4509 ms 18496 KB Output is correct
16 Correct 5631 ms 22176 KB Output is correct
17 Execution timed out 8036 ms 21472 KB Time limit exceeded