oj.uz

Submission #524198

# Submission time Handle Problem Language Result Execution time Memory
524198 2022-02-08T18:44:36 Z keertan Regions (IOI09_regions) C++17
0 / 100
 8000 ms 26584 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()<=250000){
            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 10 ms 6984 KB Execution killed with signal 13
6 Runtime error 21 ms 6984 KB Execution killed with signal 13
7 Runtime error 33 ms 6984 KB Execution killed with signal 13
8 Runtime error 38 ms 6984 KB Execution killed with signal 13
9 Runtime error 39 ms 7368 KB Execution killed with signal 13
10 Runtime error 74 ms 7368 KB Execution killed with signal 13
11 Runtime error 70 ms 7680 KB Execution killed with signal 13
12 Runtime error 161 ms 8136 KB Execution killed with signal 13
13 Runtime error 197 ms 7908 KB Execution killed with signal 13
14 Runtime error 265 ms 8392 KB Execution killed with signal 13
15 Runtime error 296 ms 10952 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8069 ms 11476 KB Time limit exceeded
2 Execution timed out 8098 ms 10308 KB Time limit exceeded
3 Execution timed out 8037 ms 13292 KB Time limit exceeded
4 Runtime error 270 ms 8520 KB Execution killed with signal 13
5 Runtime error 376 ms 10072 KB Execution killed with signal 13
6 Runtime error 1251 ms 9648 KB Execution killed with signal 13
7 Runtime error 1637 ms 10560 KB Execution killed with signal 13
8 Runtime error 1361 ms 15476 KB Execution killed with signal 13
9 Runtime error 2649 ms 15656 KB Execution killed with signal 13
10 Runtime error 4594 ms 20532 KB Execution killed with signal 13
11 Runtime error 3940 ms 15424 KB Execution killed with signal 13
12 Runtime error 5743 ms 17220 KB Execution killed with signal 13
13 Runtime error 6596 ms 17424 KB Execution killed with signal 13
14 Execution timed out 8086 ms 17032 KB Time limit exceeded
15 Execution timed out 8042 ms 21196 KB Time limit exceeded
16 Execution timed out 8061 ms 26584 KB Time limit exceeded
17 Execution timed out 8013 ms 25400 KB Time limit exceeded