oj.uz

Submission #914236

# Submission time Handle Problem Language Result Execution time Memory
914236 2024-01-21T12:05:34 Z VMaksimoski008 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 26232 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int maxn = 1e5 + 5;

int n, r, q, home[maxn], timer = 0, curr = 1;
vector<vector<int> > graph;
vector<vector<pii> > by_home;
int in[maxn], out[maxn], dp[320][25005], id[maxn];

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;
    int B = static_cast<int>(sqrt(n));
    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(by_home[i].begin(), by_home[i].end());
        if(by_home[i].size() <= B) continue;
        id[i] = curr;
        dfs2(1, i, 0);
        curr++;
    }

    while(q--) {
        int r1, r2;
        cin >> r1 >> r2;

        if(by_home[r1].size() <= B) {
            int ans = 0;

            for(pii &u : by_home[r1]) {
                int l=0, r=by_home[r2].size()-1, p1 = 1e9, p2 = 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;
                }
            
                l=p1, r=by_home[r2].size()-1;
                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(p1 != 1e9 && p2 != 1e9) ans += (p2 - p1 + 1);
            }

            cout << ans << endl;
        } else {
            cout << dp[id[r1]][r2] << endl;
        }
    }

    return 0;
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:49:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if(by_home[i].size() <= B) continue;
      |            ~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:59:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if(by_home[r1].size() <= B) {
      |            ~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 12 ms 600 KB Output is correct
9 Correct 21 ms 856 KB Output is correct
10 Correct 38 ms 1112 KB Output is correct
11 Correct 60 ms 1496 KB Output is correct
12 Correct 77 ms 2136 KB Output is correct
13 Correct 82 ms 1880 KB Output is correct
14 Correct 136 ms 4864 KB Output is correct
15 Correct 152 ms 7644 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 11000 KB Output is correct
2 Correct 1069 ms 7892 KB Output is correct
3 Correct 1785 ms 11340 KB Output is correct
4 Correct 128 ms 2864 KB Output is correct
5 Correct 200 ms 4332 KB Output is correct
6 Correct 336 ms 10848 KB Output is correct
7 Correct 662 ms 12356 KB Output is correct
8 Correct 660 ms 22016 KB Output is correct
9 Execution timed out 8051 ms 8828 KB Time limit exceeded
10 Runtime error 33 ms 21668 KB Execution killed with signal 11
11 Runtime error 28 ms 17632 KB Execution killed with signal 11
12 Incorrect 32 ms 11976 KB Unexpected end of file - int32 expected
13 Runtime error 42 ms 23788 KB Execution killed with signal 11
14 Execution timed out 8009 ms 12060 KB Time limit exceeded
15 Runtime error 32 ms 22704 KB Execution killed with signal 11
16 Runtime error 36 ms 26232 KB Execution killed with signal 11
17 Incorrect 30 ms 15476 KB Unexpected end of file - int32 expected