oj.uz

Submission #967576

# Submission time Handle Problem Language Result Execution time Memory
967576 2024-04-22T13:04:34 Z 12345678 Regions (IOI09_regions) C++17
70 / 100
 8000 ms 21844 KB 
#include <bits/stdc++.h>

using namespace std;

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

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>>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<<'\n';
        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 8536 KB Output is correct
4 Correct 5 ms 8652 KB Output is correct
5 Correct 6 ms 8536 KB Output is correct
6 Correct 10 ms 8536 KB Output is correct
7 Correct 16 ms 8536 KB Output is correct
8 Correct 17 ms 8536 KB Output is correct
9 Correct 34 ms 8792 KB Output is correct
10 Correct 62 ms 8792 KB Output is correct
11 Correct 100 ms 9048 KB Output is correct
12 Correct 124 ms 9580 KB Output is correct
13 Correct 166 ms 9308 KB Output is correct
14 Correct 249 ms 9744 KB Output is correct
15 Correct 333 ms 11272 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1567 ms 13280 KB Output is correct
2 Correct 1719 ms 12904 KB Output is correct
3 Correct 2985 ms 14892 KB Output is correct
4 Correct 274 ms 9768 KB Output is correct
5 Correct 317 ms 10788 KB Output is correct
6 Correct 1234 ms 10540 KB Output is correct
7 Correct 1768 ms 11152 KB Output is correct
8 Correct 1795 ms 14424 KB Output is correct
9 Correct 2633 ms 14968 KB Output is correct
10 Correct 4754 ms 17968 KB Output is correct
11 Correct 4310 ms 14456 KB Output is correct
12 Execution timed out 8080 ms 16272 KB Time limit exceeded
13 Execution timed out 8021 ms 16368 KB Time limit exceeded
14 Execution timed out 8029 ms 16412 KB Time limit exceeded
15 Execution timed out 8054 ms 18888 KB Time limit exceeded
16 Execution timed out 8005 ms 21832 KB Time limit exceeded
17 Execution timed out 8045 ms 21844 KB Time limit exceeded