oj.uz

Submission #967866

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

using namespace std;

const int nx=2e5+5, k=450, 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 8536 KB Output is correct
4 Correct 4 ms 8536 KB Output is correct
5 Correct 5 ms 8536 KB Output is correct
6 Correct 15 ms 8536 KB Output is correct
7 Correct 20 ms 8536 KB Output is correct
8 Correct 21 ms 8536 KB Output is correct
9 Correct 28 ms 9048 KB Output is correct
10 Correct 51 ms 9048 KB Output is correct
11 Correct 91 ms 9048 KB Output is correct
12 Correct 101 ms 9560 KB Output is correct
13 Correct 141 ms 9332 KB Output is correct
14 Correct 249 ms 9564 KB Output is correct
15 Correct 306 ms 11612 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 15020 KB Output is correct
2 Correct 1750 ms 13416 KB Output is correct
3 Correct 2888 ms 15056 KB Output is correct
4 Correct 272 ms 10052 KB Output is correct
5 Correct 299 ms 10896 KB Output is correct
6 Execution timed out 8018 ms 20764 KB Time limit exceeded
7 Correct 4232 ms 14036 KB Output is correct
8 Execution timed out 8007 ms 22024 KB Time limit exceeded
9 Correct 2685 ms 15056 KB Output is correct
10 Execution timed out 8023 ms 21308 KB Time limit exceeded
11 Correct 4895 ms 14616 KB Output is correct
12 Execution timed out 8012 ms 16452 KB Time limit exceeded
13 Execution timed out 8022 ms 16452 KB Time limit exceeded
14 Execution timed out 8058 ms 16468 KB Time limit exceeded
15 Execution timed out 8007 ms 19104 KB Time limit exceeded
16 Execution timed out 8074 ms 22628 KB Time limit exceeded
17 Execution timed out 8058 ms 22448 KB Time limit exceeded