oj.uz

Submission #914237

# Submission time Handle Problem Language Result Execution time Memory
914237 2024-01-21T12:10:56 Z VMaksimoski008 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 29560 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, i, r1, r2, ans, L, R, p1, p2, mid;
vector<vector<int> > graph;
vector<vector<pii> > by_home;
int in[maxn], out[maxn], dp[330][25001], 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(i=2; i<=n; i++) {
        int p;
        cin >> p >> home[i];
        graph[p].push_back(i);
    }

    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(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--) {
        cin >> r1 >> r2;

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

            for(pii &u : by_home[r1]) {
                L=0, R=by_home[r2].size()-1, p1 = 1e9, p2 = 1e9;
 
                while(L <= R) {
                    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) {
                    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:58: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]
   58 |         if(by_home[r1].size() <= B) {
      |            ~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2804 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 4 ms 2392 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 14 ms 2392 KB Output is correct
8 Correct 15 ms 2648 KB Output is correct
9 Correct 21 ms 2904 KB Output is correct
10 Correct 38 ms 3160 KB Output is correct
11 Correct 60 ms 3416 KB Output is correct
12 Correct 73 ms 4156 KB Output is correct
13 Correct 83 ms 3928 KB Output is correct
14 Correct 125 ms 6816 KB Output is correct
15 Correct 185 ms 9528 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1135 ms 12764 KB Output is correct
2 Correct 1099 ms 9644 KB Output is correct
3 Correct 1853 ms 12852 KB Output is correct
4 Correct 154 ms 4792 KB Output is correct
5 Correct 205 ms 6080 KB Output is correct
6 Correct 342 ms 12696 KB Output is correct
7 Correct 697 ms 14136 KB Output is correct
8 Correct 733 ms 24232 KB Output is correct
9 Execution timed out 8042 ms 10740 KB Time limit exceeded
10 Runtime error 35 ms 25400 KB Execution killed with signal 11
11 Runtime error 32 ms 20956 KB Execution killed with signal 11
12 Incorrect 28 ms 13456 KB Unexpected end of file - int32 expected
13 Runtime error 40 ms 27248 KB Execution killed with signal 11
14 Execution timed out 8032 ms 13432 KB Time limit exceeded
15 Runtime error 34 ms 26228 KB Execution killed with signal 11
16 Runtime error 36 ms 29560 KB Execution killed with signal 11
17 Incorrect 31 ms 17376 KB Unexpected end of file - int32 expected