oj.uz

Submission #967571

# Submission time Handle Problem Language Result Execution time Memory
967571 2024-04-22T12:57:16 Z 12345678 Regions (IOI09_regions) C++17
40 / 100
 8000 ms 22584 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, k=300, 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 3 ms 8536 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 4 ms 8632 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 16 ms 8620 KB Output is correct
7 Correct 21 ms 8536 KB Output is correct
8 Correct 31 ms 8536 KB Output is correct
9 Correct 33 ms 8792 KB Output is correct
10 Correct 58 ms 8792 KB Output is correct
11 Correct 98 ms 9040 KB Output is correct
12 Correct 106 ms 9408 KB Output is correct
13 Correct 162 ms 9308 KB Output is correct
14 Correct 252 ms 9588 KB Output is correct
15 Correct 313 ms 11328 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1511 ms 16296 KB Output is correct
2 Correct 1799 ms 13348 KB Output is correct
3 Correct 3090 ms 14696 KB Output is correct
4 Correct 256 ms 9768 KB Output is correct
5 Correct 338 ms 10788 KB Output is correct
6 Execution timed out 8023 ms 20916 KB Time limit exceeded
7 Execution timed out 8036 ms 20296 KB Time limit exceeded
8 Execution timed out 8082 ms 21972 KB Time limit exceeded
9 Execution timed out 8016 ms 22584 KB Time limit exceeded
10 Execution timed out 8080 ms 21252 KB Time limit exceeded
11 Execution timed out 8067 ms 18744 KB Time limit exceeded
12 Execution timed out 8073 ms 16488 KB Time limit exceeded
13 Execution timed out 8032 ms 16264 KB Time limit exceeded
14 Execution timed out 8093 ms 16356 KB Time limit exceeded
15 Execution timed out 8013 ms 18880 KB Time limit exceeded
16 Execution timed out 8054 ms 21820 KB Time limit exceeded
17 Execution timed out 8090 ms 21924 KB Time limit exceeded