oj.uz

Submission #524197

# Submission time Handle Problem Language Result Execution time Memory
524197 2022-02-08T18:42:14 Z keertan Regions (IOI09_regions) C++17
0 / 100
 8000 ms 26564 KB 
// Check sqrt decomposition CPH to understand this solution well
// Basically combined two solutions, one works well for regions with smaller size
// The other works well for regions with larger size
// Set the line between larger and smaller as sqrt(n) or so and apply the appropriate algo for best results
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
bool vis[25001];
int n,r,q,cnt=1, a[maxn], st[maxn], en[maxn], B[maxn];
unordered_map<int,int> calc[25001];
vector<int> adj[maxn], v[25001];
void dfs(int s, int p = -1)
{
    st[s] = cnt++;
    for(auto u : adj[s])
        if(u!=p) dfs(u,s);
    en[s] = cnt-1;
}

int32_t main()
{
    cin >> n >> r >> q >> a[1];
    for(int i = 2; i <= n; i++)
    {
        int x; cin >> x >> a[i];
        adj[x].push_back(i);
    }
    int K = sqrt(n);
    dfs(1); for(int i = 1; i <= n; i++) B[st[i]]=i;
    for(int i = 1; i <= n; i++) v[a[B[i]]].push_back(st[B[i]]);
    for(int i = 1; i <= n; i++)
    while(q--)
    {
        int a, b, ans = 0; cin >> a >> b;
        if(v[a].size()<=1e9){
            for(auto u : v[a]){
                int l = st[B[u]], r = en[B[u]];
                auto itr = upper_bound(v[b].begin(), v[b].end(), r)-v[b].begin();
                auto itr2 = upper_bound(v[b].begin(), v[b].end(), l)-v[b].begin();
                if(itr) itr--, ans+=max((int)(itr-itr2)+1, 0);
            }
        }
        else ans = calc[b][a];
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:28:9: warning: unused variable 'K' [-Wunused-variable]
   28 |     int K = sqrt(n);
      |         ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 6856 KB Execution killed with signal 13
2 Runtime error 3 ms 6856 KB Execution killed with signal 13
3 Runtime error 5 ms 6856 KB Execution killed with signal 13
4 Runtime error 7 ms 6856 KB Execution killed with signal 13
5 Runtime error 11 ms 6984 KB Execution killed with signal 13
6 Runtime error 21 ms 6984 KB Execution killed with signal 13
7 Runtime error 31 ms 6984 KB Execution killed with signal 13
8 Runtime error 36 ms 6984 KB Execution killed with signal 13
9 Runtime error 44 ms 7368 KB Execution killed with signal 13
10 Runtime error 81 ms 7368 KB Execution killed with signal 13
11 Runtime error 131 ms 7752 KB Execution killed with signal 13
12 Runtime error 136 ms 8288 KB Execution killed with signal 13
13 Runtime error 158 ms 7876 KB Execution killed with signal 13
14 Runtime error 249 ms 8520 KB Execution killed with signal 13
15 Runtime error 305 ms 10944 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8080 ms 11480 KB Time limit exceeded
2 Execution timed out 8022 ms 10304 KB Time limit exceeded
3 Execution timed out 8022 ms 13252 KB Time limit exceeded
4 Runtime error 294 ms 8468 KB Execution killed with signal 13
5 Runtime error 355 ms 10056 KB Execution killed with signal 13
6 Runtime error 1278 ms 9792 KB Execution killed with signal 13
7 Runtime error 1695 ms 10560 KB Execution killed with signal 13
8 Runtime error 1401 ms 15472 KB Execution killed with signal 13
9 Runtime error 2423 ms 15680 KB Execution killed with signal 13
10 Runtime error 4008 ms 20524 KB Execution killed with signal 13
11 Runtime error 3884 ms 15420 KB Execution killed with signal 13
12 Runtime error 5044 ms 17096 KB Execution killed with signal 13
13 Runtime error 5681 ms 17256 KB Execution killed with signal 13
14 Runtime error 7308 ms 16952 KB Execution killed with signal 13
15 Execution timed out 8048 ms 21288 KB Time limit exceeded
16 Execution timed out 8028 ms 26564 KB Time limit exceeded
17 Execution timed out 8079 ms 25500 KB Time limit exceeded