oj.uz

Submission #964829

# Submission time Handle Problem Language Result Execution time Memory
964829 2024-04-17T15:49:43 Z codefox Regions (IOI09_regions) C++14
25 / 100
 561 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

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

#define pii pair<int, short>

vector<vector<int>> graph;
vector<short> 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 = 440;

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));


    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++;
        }
    }

    rsum.resize(0);
    dfsback(0);
    dpback.resize(0);
    frontsolutions.assign(K, vector<int>(r, -1));
    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 344 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 5 ms 1368 KB Output is correct
6 Correct 13 ms 2648 KB Output is correct
7 Correct 18 ms 3416 KB Output is correct
8 Correct 24 ms 4440 KB Output is correct
9 Correct 54 ms 11040 KB Output is correct
10 Correct 91 ms 19524 KB Output is correct
11 Correct 152 ms 28436 KB Output is correct
12 Correct 189 ms 38316 KB Output is correct
13 Correct 267 ms 44680 KB Output is correct
14 Correct 448 ms 55684 KB Output is correct
15 Correct 496 ms 78364 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 131072 KB Execution killed with signal 9
2 Runtime error 52 ms 131072 KB Execution killed with signal 9
3 Runtime error 59 ms 131072 KB Execution killed with signal 9
4 Correct 428 ms 62604 KB Output is correct
5 Correct 484 ms 79596 KB Output is correct
6 Incorrect 561 ms 108504 KB Output isn't correct
7 Runtime error 50 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 52 ms 131072 KB Execution killed with signal 9
11 Runtime error 53 ms 131072 KB Execution killed with signal 9
12 Runtime error 49 ms 131072 KB Execution killed with signal 9
13 Runtime error 50 ms 131072 KB Execution killed with signal 9
14 Runtime error 52 ms 131072 KB Execution killed with signal 9
15 Runtime error 52 ms 131072 KB Execution killed with signal 9
16 Runtime error 51 ms 131072 KB Execution killed with signal 9
17 Runtime error 57 ms 131072 KB Execution killed with signal 9