oj.uz

Submission #967868

# Submission time Handle Problem Language Result Execution time Memory
967868 2024-04-23T03:20:07 Z 12345678 Regions (IOI09_regions) C++17
70 / 100
 8000 ms 22556 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, k=500, kx=25005;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int n, x, q, p, in[nx], out[nx], t, a, b, sz, res;
vector<int> d[nx], r[kx], vin[kx], vout[kx];

struct fenwick
{
    int d[nx];
    void update(int i, int vl) {while (i<nx) d[i]+=vl, i+=(i&-i);}
    int query(int i)
    {
        int res=0;
        while (i>0) res+=d[i], i-=(i&-i);
        return res;
    }
} f;

void dfs(int u)
{
    in[u]=++t;
    for (auto v:d[u]) dfs(v);
    out[u]=t;
}

int bruteforce(int a, int b)
{
    for (auto x:r[b]) f.update(in[x], 1);
    int res=0;
    for (auto x:r[a]) res+=f.query(out[x])-f.query(in[x]-1);
    for (auto x:r[b]) f.update(in[x], -1);
    return res;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>sz>>q;
    cin>>x;
    r[x].push_back(1);
    for (int i=2; i<=n; i++) cin>>p>>x, d[p].push_back(i), r[x].push_back(i);
    dfs(1);
    for (int i=1; i<=sz; i++)
    {
        if (r[i].size()>=k)
        {
            vin[i].resize(kx);
            vout[i].resize(kx);
            for (int j=1; j<=sz; j++) if (i!=j) vin[i][j]=bruteforce(i, j), vout[i][j]=bruteforce(j, i);
        }
    }
    while (q--)
    {
        cin>>a>>b;
        if (r[a].size()>=k) res=vin[a][b];
        else if (r[b].size()>=k) res=vout[b][a];
        else res=bruteforce(a, b);
        cout<<res<<endl;
        fflush(stdout);
    }
}

/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 3 ms 8548 KB Output is correct
4 Correct 5 ms 8536 KB Output is correct
5 Correct 7 ms 8536 KB Output is correct
6 Correct 16 ms 7000 KB Output is correct
7 Correct 25 ms 7000 KB Output is correct
8 Correct 29 ms 7252 KB Output is correct
9 Correct 37 ms 7256 KB Output is correct
10 Correct 54 ms 8864 KB Output is correct
11 Correct 105 ms 9056 KB Output is correct
12 Correct 119 ms 9524 KB Output is correct
13 Correct 180 ms 9328 KB Output is correct
14 Correct 294 ms 9692 KB Output is correct
15 Correct 340 ms 11336 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1792 ms 14228 KB Output is correct
2 Correct 1916 ms 13412 KB Output is correct
3 Correct 3273 ms 14648 KB Output is correct
4 Correct 315 ms 9792 KB Output is correct
5 Correct 320 ms 11164 KB Output is correct
6 Correct 4384 ms 14364 KB Output is correct
7 Correct 2196 ms 11192 KB Output is correct
8 Correct 2911 ms 15324 KB Output is correct
9 Correct 3466 ms 14932 KB Output is correct
10 Correct 5730 ms 18524 KB Output is correct
11 Correct 4573 ms 14496 KB Output is correct
12 Execution timed out 8089 ms 16456 KB Time limit exceeded
13 Execution timed out 8098 ms 16568 KB Time limit exceeded
14 Execution timed out 8045 ms 16412 KB Time limit exceeded
15 Execution timed out 8039 ms 19436 KB Time limit exceeded
16 Execution timed out 8022 ms 22556 KB Time limit exceeded
17 Execution timed out 8012 ms 22440 KB Time limit exceeded