oj.uz

Submission #914016

# Submission time Handle Problem Language Result Execution time Memory
914016 2024-01-20T19:17:47 Z VMaksimoski008 Regions (IOI09_regions) C++14
0 / 100
 77 ms 22288 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 2 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 2 ms 2648 KB Time limit exceeded (wall clock)
9 Execution timed out 2 ms 2900 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 3160 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 3472 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 4044 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 3956 KB Time limit exceeded (wall clock)
14 Execution timed out 8 ms 4468 KB Time limit exceeded (wall clock)
15 Execution timed out 9 ms 6620 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 22 ms 8196 KB Time limit exceeded (wall clock)
2 Execution timed out 23 ms 6876 KB Time limit exceeded (wall clock)
3 Execution timed out 22 ms 9584 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 4440 KB Time limit exceeded (wall clock)
5 Execution timed out 9 ms 5828 KB Time limit exceeded (wall clock)
6 Execution timed out 14 ms 6160 KB Time limit exceeded (wall clock)
7 Execution timed out 23 ms 7328 KB Time limit exceeded (wall clock)
8 Execution timed out 30 ms 11684 KB Time limit exceeded (wall clock)
9 Execution timed out 48 ms 13880 KB Time limit exceeded (wall clock)
10 Execution timed out 56 ms 17284 KB Time limit exceeded (wall clock)
11 Execution timed out 64 ms 14244 KB Time limit exceeded (wall clock)
12 Execution timed out 77 ms 15560 KB Time limit exceeded (wall clock)
13 Execution timed out 60 ms 15644 KB Time limit exceeded (wall clock)
14 Execution timed out 62 ms 15900 KB Time limit exceeded (wall clock)
15 Execution timed out 60 ms 19244 KB Time limit exceeded (wall clock)
16 Execution timed out 47 ms 22288 KB Time limit exceeded (wall clock)
17 Execution timed out 68 ms 21584 KB Time limit exceeded (wall clock)