oj.uz

Submission #967854

# Submission time Handle Problem Language Result Execution time Memory
967854 2024-04-23T02:43:25 Z 12345678 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 22528 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()
{
    scanf("%d %d %d", &n, &sz, &q);
    scanf("%d", &x);
    r[x].push_back(1);
    for (int i=2; i<=n; i++) scanf("%d %d", &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--)
    {
        scanf("%d %d", &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);
        printf("%d\n", res);
        fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d %d %d", &n, &sz, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~
regions.cpp:46:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     for (int i=2; i<=n; i++) scanf("%d %d", &p, &x), d[p].push_back(i), r[x].push_back(i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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 4 ms 8536 KB Output is correct
5 Correct 5 ms 8624 KB Output is correct
6 Correct 10 ms 8536 KB Output is correct
7 Correct 19 ms 8536 KB Output is correct
8 Correct 18 ms 8536 KB Output is correct
9 Correct 30 ms 8792 KB Output is correct
10 Correct 62 ms 9048 KB Output is correct
11 Correct 105 ms 9048 KB Output is correct
12 Correct 117 ms 9560 KB Output is correct
13 Correct 155 ms 9312 KB Output is correct
14 Correct 262 ms 9616 KB Output is correct
15 Correct 298 ms 11352 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1581 ms 14888 KB Output is correct
2 Correct 1791 ms 13244 KB Output is correct
3 Correct 3017 ms 15056 KB Output is correct
4 Correct 293 ms 9772 KB Output is correct
5 Correct 303 ms 10880 KB Output is correct
6 Execution timed out 8054 ms 20892 KB Time limit exceeded
7 Correct 4353 ms 14012 KB Output is correct
8 Execution timed out 8023 ms 22288 KB Time limit exceeded
9 Correct 2820 ms 15036 KB Output is correct
10 Execution timed out 8083 ms 21856 KB Time limit exceeded
11 Correct 5049 ms 14616 KB Output is correct
12 Execution timed out 8037 ms 16420 KB Time limit exceeded
13 Execution timed out 8067 ms 16216 KB Time limit exceeded
14 Execution timed out 8076 ms 16384 KB Time limit exceeded
15 Execution timed out 8058 ms 19560 KB Time limit exceeded
16 Execution timed out 8012 ms 22528 KB Time limit exceeded
17 Execution timed out 8067 ms 22408 KB Time limit exceeded