oj.uz

Submission #914018

# Submission time Handle Problem Language Result Execution time Memory
914018 2024-01-20T19:21:36 Z VMaksimoski008 Regions (IOI09_regions) C++14
0 / 100
 64 ms 22304 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int n, r, q, home[maxn], in[maxn], out[maxn], timer = 0;
vector<vector<int> > graph;
vector<vector<pii> > by_home;

void dfs(int u) {
    in[u] = timer++;

    for(int &v : graph[u])
        dfs(v);

    out[u] = timer;
}

int32_t main() {
    setIO();

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

    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';
    }
    
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 2392 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 2392 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 2392 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 2392 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 2392 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 2392 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 2392 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 2648 KB Time limit exceeded (wall clock)
9 Execution timed out 2 ms 2904 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 3160 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 3416 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 3928 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 3712 KB Time limit exceeded (wall clock)
14 Execution timed out 9 ms 4488 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 6852 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 17 ms 7860 KB Time limit exceeded (wall clock)
2 Execution timed out 23 ms 6984 KB Time limit exceeded (wall clock)
3 Execution timed out 20 ms 9648 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 4440 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 5944 KB Time limit exceeded (wall clock)
6 Execution timed out 15 ms 6204 KB Time limit exceeded (wall clock)
7 Execution timed out 17 ms 7416 KB Time limit exceeded (wall clock)
8 Execution timed out 23 ms 11932 KB Time limit exceeded (wall clock)
9 Execution timed out 52 ms 14000 KB Time limit exceeded (wall clock)
10 Execution timed out 43 ms 17912 KB Time limit exceeded (wall clock)
11 Execution timed out 54 ms 14396 KB Time limit exceeded (wall clock)
12 Execution timed out 64 ms 15976 KB Time limit exceeded (wall clock)
13 Execution timed out 56 ms 15704 KB Time limit exceeded (wall clock)
14 Execution timed out 64 ms 15764 KB Time limit exceeded (wall clock)
15 Execution timed out 51 ms 19148 KB Time limit exceeded (wall clock)
16 Execution timed out 50 ms 22304 KB Time limit exceeded (wall clock)
17 Execution timed out 46 ms 21820 KB Time limit exceeded (wall clock)