oj.uz

Submission #967855

# Submission time Handle Problem Language Result Execution time Memory
967855 2024-04-23T02:44:18 Z 12345678 Regions (IOI09_regions) C++17
70 / 100
 8000 ms 22540 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, k=500, 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);
    }
}

/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
*/

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 3 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 9 ms 8536 KB Output is correct
6 Correct 15 ms 8536 KB Output is correct
7 Correct 17 ms 8536 KB Output is correct
8 Correct 27 ms 8788 KB Output is correct
9 Correct 34 ms 8792 KB Output is correct
10 Correct 57 ms 8792 KB Output is correct
11 Correct 93 ms 9304 KB Output is correct
12 Correct 114 ms 9560 KB Output is correct
13 Correct 170 ms 9304 KB Output is correct
14 Correct 286 ms 9584 KB Output is correct
15 Correct 333 ms 11352 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1627 ms 13988 KB Output is correct
2 Correct 1704 ms 13308 KB Output is correct
3 Correct 3136 ms 14808 KB Output is correct
4 Correct 297 ms 9776 KB Output is correct
5 Correct 323 ms 10880 KB Output is correct
6 Correct 3862 ms 14116 KB Output is correct
7 Correct 1894 ms 11192 KB Output is correct
8 Correct 2486 ms 15420 KB Output is correct
9 Correct 2842 ms 15036 KB Output is correct
10 Correct 5135 ms 18480 KB Output is correct
11 Correct 5151 ms 14620 KB Output is correct
12 Execution timed out 8100 ms 16440 KB Time limit exceeded
13 Execution timed out 8086 ms 16236 KB Time limit exceeded
14 Execution timed out 8016 ms 16444 KB Time limit exceeded
15 Execution timed out 8029 ms 19220 KB Time limit exceeded
16 Execution timed out 8018 ms 22540 KB Time limit exceeded
17 Execution timed out 8096 ms 22420 KB Time limit exceeded