oj.uz

Submission #914238

# Submission time Handle Problem Language Result Execution time Memory
914238 2024-01-21T12:14:26 Z VMaksimoski008 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 26268 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[210][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 = 500;
    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 344 KB Output is correct
2 Correct 1 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 3 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 11 ms 344 KB Output is correct
8 Correct 14 ms 600 KB Output is correct
9 Correct 21 ms 856 KB Output is correct
10 Correct 41 ms 1252 KB Output is correct
11 Correct 61 ms 1624 KB Output is correct
12 Correct 93 ms 2136 KB Output is correct
13 Correct 97 ms 1920 KB Output is correct
14 Correct 140 ms 2812 KB Output is correct
15 Correct 185 ms 5256 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1181 ms 8964 KB Output is correct
2 Correct 1139 ms 7888 KB Output is correct
3 Correct 1925 ms 11376 KB Output is correct
4 Correct 139 ms 2864 KB Output is correct
5 Correct 195 ms 4300 KB Output is correct
6 Correct 792 ms 4584 KB Output is correct
7 Correct 935 ms 6088 KB Output is correct
8 Correct 763 ms 10804 KB Output is correct
9 Execution timed out 8090 ms 8744 KB Time limit exceeded
10 Runtime error 38 ms 21684 KB Execution killed with signal 11
11 Runtime error 30 ms 17860 KB Execution killed with signal 11
12 Incorrect 35 ms 11788 KB Unexpected end of file - int32 expected
13 Runtime error 34 ms 24132 KB Execution killed with signal 11
14 Execution timed out 8037 ms 11704 KB Time limit exceeded
15 Runtime error 42 ms 22912 KB Execution killed with signal 11
16 Runtime error 45 ms 26268 KB Execution killed with signal 11
17 Incorrect 32 ms 12408 KB Unexpected end of file - int32 expected