oj.uz

Submission #964825

# Submission time Handle Problem Language Result Execution time Memory
964825 2024-04-17T15:43:51 Z codefox Regions (IOI09_regions) C++14
25 / 100
 514 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> start;
vector<int> ende;
int c =0 ;

vector<vector<int>> dpback;

vector<vector<int>> backsolutions;
vector<vector<int>> frontsolutions;

int K = 500;

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++)
    {
        backsolutions[region[i]][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++)
    {
        frontsolutions[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);
    start.assign(n, 0);
    ende.assign(n, 0);
    dpback.assign(n, vector<int>(K, 0));
    backsolutions.assign(r, vector<int>(K, -1));
    frontsolutions.assign(K, 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;
        graph[b-1].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) 
        {
            rind[i] = d++;
        }
    }

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

    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (rsum[a]>K) cout << frontsolutions[rind[a]][b] << endl;
        else if (rsum[b]>K) cout << backsolutions[a][rind[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 600 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 7 ms 1624 KB Output is correct
6 Correct 13 ms 3160 KB Output is correct
7 Correct 23 ms 3928 KB Output is correct
8 Correct 30 ms 5208 KB Output is correct
9 Correct 50 ms 12336 KB Output is correct
10 Correct 105 ms 22828 KB Output is correct
11 Correct 174 ms 32604 KB Output is correct
12 Correct 205 ms 44060 KB Output is correct
13 Correct 276 ms 51128 KB Output is correct
14 Correct 479 ms 63240 KB Output is correct
15 Correct 506 ms 87956 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 131072 KB Execution killed with signal 9
2 Runtime error 50 ms 131072 KB Execution killed with signal 9
3 Runtime error 53 ms 131072 KB Execution killed with signal 9
4 Correct 431 ms 78504 KB Output is correct
5 Correct 514 ms 99340 KB Output is correct
6 Runtime error 50 ms 131072 KB Execution killed with signal 9
7 Runtime error 53 ms 131072 KB Execution killed with signal 9
8 Runtime error 51 ms 131072 KB Execution killed with signal 9
9 Runtime error 56 ms 131072 KB Execution killed with signal 9
10 Runtime error 56 ms 131072 KB Execution killed with signal 9
11 Runtime error 49 ms 131072 KB Execution killed with signal 9
12 Runtime error 51 ms 131072 KB Execution killed with signal 9
13 Runtime error 65 ms 131072 KB Execution killed with signal 9
14 Runtime error 50 ms 131072 KB Execution killed with signal 9
15 Runtime error 62 ms 131072 KB Execution killed with signal 9
16 Runtime error 54 ms 131072 KB Execution killed with signal 9
17 Runtime error 52 ms 131072 KB Execution killed with signal 9