oj.uz

답안 #967578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967578 2024-04-22T13:08:13 Z 12345678 Regions (IOI09_regions) C++17
40 / 100
 8000 ms 64212 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, k=160, 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>>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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 4 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 7 ms 8536 KB Output is correct
6 Correct 11 ms 8664 KB Output is correct
7 Correct 15 ms 8536 KB Output is correct
8 Correct 20 ms 8544 KB Output is correct
9 Correct 35 ms 8792 KB Output is correct
10 Correct 60 ms 8792 KB Output is correct
11 Correct 97 ms 9080 KB Output is correct
12 Correct 116 ms 9560 KB Output is correct
13 Correct 179 ms 9312 KB Output is correct
14 Correct 350 ms 18600 KB Output is correct
15 Correct 797 ms 44584 KB Output is correct

Subtask #2
25.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2298 ms 50644 KB Output is correct
2 Correct 2522 ms 43116 KB Output is correct
3 Correct 3757 ms 64212 KB Output is correct
4 Correct 955 ms 15064 KB Output is correct
5 Correct 316 ms 10872 KB Output is correct
6 Execution timed out 8007 ms 20728 KB Time limit exceeded
7 Execution timed out 8100 ms 21880 KB Time limit exceeded
8 Execution timed out 8007 ms 21924 KB Time limit exceeded
9 Execution timed out 8016 ms 22920 KB Time limit exceeded
10 Execution timed out 8034 ms 24388 KB Time limit exceeded
11 Execution timed out 8004 ms 19400 KB Time limit exceeded
12 Execution timed out 8010 ms 26336 KB Time limit exceeded
13 Execution timed out 8023 ms 26320 KB Time limit exceeded
14 Execution timed out 8098 ms 20496 KB Time limit exceeded
15 Execution timed out 8069 ms 25936 KB Time limit exceeded
16 Execution timed out 8090 ms 28280 KB Time limit exceeded
17 Execution timed out 8021 ms 26468 KB Time limit exceeded