oj.uz

Submission #964817

# Submission time Handle Problem Language Result Execution time Memory
964817 2024-04-17T15:34:10 Z codefox Regions (IOI09_regions) C++14
20 / 100
 1630 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#define pii pair<int, int>

vector<vector<int>> graph;
vector<int> region;
vector<int> rind;
vector<int> rrind;

vector<int> start;
vector<int> ende;
int c =0 ;

vector<vector<int>> dpback;

vector<vector<int>> solutions;

int K = 350;

void dfsback(int i)
{
    start[i] = c++;
    for (int ele:graph[i])
    {
        dfsback(ele);
        for (int j = 0; j < K; j++)
        {
            dpback[i][j] += dpback[ele][j];
        }
    }
    for (int j = 0; j < K; j++)
    {
        if (rrind[j]==-1) break;
        solutions[region[i]][rrind[j]] = dpback[i][j];
    }
    if (rind[region[i]]!= -1) dpback[i][rind[region[i]]]++;
    ende[i] = c;
}

void dfsfront(int i, vector<int> dpfront)
{
    for (int j = 0; j < K; j++)
    {
        if (rrind[j]==-1) break;
        solutions[rrind[j]][region[i]] = dpfront[j];
    }
    if (rind[region[i]]!=-1) dpfront[rind[region[i]]]++;
    for (int ele:graph[i])
    {
        dfsfront(ele, dpfront);
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, r, q;
    cin >> n >> r >> q;

    graph.assign(n, vector<int>());
    region.assign(n, 0);
    rind.assign(r, -1);
    rrind.assign(K, -1);
    start.assign(n, 0);
    ende.assign(n, 0);
    dpback.assign(n, vector<int>(K, 0));
    solutions.assign(r, vector<int>(r, -1));

    vector<vector<int>> part(r);

    cin >> region[0];
    region[0]--;
    part[region[0]].push_back(0);
    for (int i = 1; i < n; i++)
    {
        int b;
        cin >> b;
        b--;
        graph[b].push_back(i);
        cin >> region[i];
        region[i]--;
        part[region[i]].push_back(i);
    }

    vector<int> rsum(r);
    int d =0;
    for (int i = 0; i < n; i++) rsum[region[i]]++;
    for (int i = 0; i < r; i++)
    {
        if (rsum[i]> K) 
        {
            rrind[d] = i;
            rind[i] = d++;
        }
    }

    dfsback(0);
    dfsfront(0, vector<int>(K, 0));

    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (solutions[a][b]!=-1) cout << solutions[a][b] << endl;
        else
        {
            vector<pii> s;
            for (int ele:part[a]) 
            {
                s.push_back({start[ele], 0});
                s.push_back({ende[ele], 1});
            }
            for (int ele:part[b])
            {
                s.push_back({start[ele], 2});
            }
            sort(s.begin(), s.end());

            int open = 0;
            int sol = 0;
            for (pii ele:s)
            {
                if (ele.second == 0) open++;
                if (ele.second == 1) open--;
                if (ele.second == 2) sol += open;
            }
            cout << sol << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 11 ms 2900 KB Output is correct
7 Correct 19 ms 2904 KB Output is correct
8 Correct 23 ms 3928 KB Output is correct
9 Correct 48 ms 15456 KB Output is correct
10 Correct 86 ms 16028 KB Output is correct
11 Correct 142 ms 23696 KB Output is correct
12 Correct 184 ms 37280 KB Output is correct
13 Correct 250 ms 36016 KB Output is correct
14 Correct 414 ms 45136 KB Output is correct
15 Correct 487 ms 118332 KB Output is correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 131072 KB Execution killed with signal 9
2 Incorrect 1630 ms 120440 KB Output isn't correct
3 Runtime error 59 ms 131072 KB Execution killed with signal 9
4 Correct 418 ms 109852 KB Output is correct
5 Runtime error 50 ms 131072 KB Execution killed with signal 9
6 Runtime error 55 ms 131072 KB Execution killed with signal 9
7 Runtime error 56 ms 131072 KB Execution killed with signal 9
8 Runtime error 53 ms 131072 KB Execution killed with signal 9
9 Runtime error 51 ms 131072 KB Execution killed with signal 9
10 Runtime error 55 ms 131072 KB Execution killed with signal 9
11 Runtime error 53 ms 131072 KB Execution killed with signal 9
12 Runtime error 50 ms 131072 KB Execution killed with signal 9
13 Runtime error 53 ms 131072 KB Execution killed with signal 9
14 Runtime error 49 ms 131072 KB Execution killed with signal 9
15 Runtime error 48 ms 131072 KB Execution killed with signal 9
16 Runtime error 51 ms 131072 KB Execution killed with signal 9
17 Runtime error 52 ms 131072 KB Execution killed with signal 9