oj.uz

Submission #524321

# Submission time Handle Problem Language Result Execution time Memory
524321 2022-02-09T04:14:43 Z keertan Regions (IOI09_regions) C++17
75 / 100
 8000 ms 26656 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]]);
  
    while(q--)
    {
        int a, b, ans = 0; cin >> a >> b;
        if(v[a].size()<=2400000){
            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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6856 KB Output is correct
2 Correct 5 ms 6856 KB Output is correct
3 Correct 8 ms 6856 KB Output is correct
4 Correct 10 ms 6912 KB Output is correct
5 Correct 16 ms 7036 KB Output is correct
6 Correct 26 ms 6984 KB Output is correct
7 Correct 36 ms 6984 KB Output is correct
8 Correct 37 ms 7048 KB Output is correct
9 Correct 47 ms 7368 KB Output is correct
10 Correct 84 ms 7368 KB Output is correct
11 Correct 150 ms 7776 KB Output is correct
12 Correct 170 ms 8208 KB Output is correct
13 Correct 197 ms 7912 KB Output is correct
14 Correct 274 ms 8392 KB Output is correct
15 Correct 341 ms 11028 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8032 ms 11456 KB Time limit exceeded
2 Execution timed out 8079 ms 10232 KB Time limit exceeded
3 Execution timed out 8053 ms 13296 KB Time limit exceeded
4 Correct 284 ms 8520 KB Output is correct
5 Correct 313 ms 10252 KB Output is correct
6 Correct 1209 ms 9644 KB Output is correct
7 Correct 1704 ms 10552 KB Output is correct
8 Correct 1230 ms 15536 KB Output is correct
9 Correct 2020 ms 15720 KB Output is correct
10 Correct 4190 ms 20544 KB Output is correct
11 Correct 3911 ms 15372 KB Output is correct
12 Correct 4969 ms 17320 KB Output is correct
13 Correct 5298 ms 17324 KB Output is correct
14 Correct 7183 ms 17064 KB Output is correct
15 Correct 7924 ms 21272 KB Output is correct
16 Execution timed out 8068 ms 26656 KB Time limit exceeded
17 Execution timed out 8058 ms 25396 KB Time limit exceeded