oj.uz

Submission #967572

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

using namespace std;

const int nx=2e5+5, k=500, 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 2 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 8 ms 8536 KB Output is correct
6 Correct 12 ms 8536 KB Output is correct
7 Correct 18 ms 8536 KB Output is correct
8 Correct 23 ms 8536 KB Output is correct
9 Correct 35 ms 8792 KB Output is correct
10 Correct 60 ms 8792 KB Output is correct
11 Correct 105 ms 9048 KB Output is correct
12 Correct 112 ms 9596 KB Output is correct
13 Correct 183 ms 9304 KB Output is correct
14 Correct 273 ms 9648 KB Output is correct
15 Correct 345 ms 11108 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1569 ms 14180 KB Output is correct
2 Correct 1809 ms 13416 KB Output is correct
3 Correct 3039 ms 14908 KB Output is correct
4 Correct 309 ms 9764 KB Output is correct
5 Correct 347 ms 11044 KB Output is correct
6 Correct 3771 ms 14320 KB Output is correct
7 Correct 1977 ms 11152 KB Output is correct
8 Correct 2468 ms 15056 KB Output is correct
9 Correct 3003 ms 14972 KB Output is correct
10 Correct 4936 ms 18088 KB Output is correct
11 Correct 5002 ms 14460 KB Output is correct
12 Execution timed out 8068 ms 16484 KB Time limit exceeded
13 Execution timed out 8103 ms 16356 KB Time limit exceeded
14 Execution timed out 8050 ms 16416 KB Time limit exceeded
15 Execution timed out 8034 ms 19156 KB Time limit exceeded
16 Execution timed out 8045 ms 21828 KB Time limit exceeded
17 Execution timed out 8063 ms 22000 KB Time limit exceeded