oj.uz

Submission #964830

# Submission time Handle Problem Language Result Execution time Memory
964830 2024-04-17T15:50:47 Z codefox Regions (IOI09_regions) C++14
3 / 100
 541 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], 2});
            }
            for (int ele:part[b])
            {
                s.push_back({start[ele], 1});
            }
            sort(s.begin(), s.end());

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

    return 0;
}

Subtask #1
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Incorrect 4 ms 600 KB Output isn't correct
5 Incorrect 5 ms 1368 KB Output isn't correct
6 Correct 12 ms 2648 KB Output is correct
7 Incorrect 20 ms 3416 KB Output isn't correct
8 Incorrect 21 ms 4440 KB Output isn't correct
9 Correct 44 ms 11156 KB Output is correct
10 Incorrect 87 ms 19504 KB Output isn't correct
11 Incorrect 154 ms 28436 KB Output isn't correct
12 Incorrect 185 ms 38320 KB Output isn't correct
13 Incorrect 272 ms 44672 KB Output isn't correct
14 Incorrect 473 ms 55784 KB Output isn't correct
15 Correct 493 ms 78188 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 131072 KB Execution killed with signal 9
2 Runtime error 55 ms 131072 KB Execution killed with signal 9
3 Runtime error 61 ms 131072 KB Execution killed with signal 9
4 Incorrect 419 ms 62612 KB Output isn't correct
5 Incorrect 491 ms 79600 KB Output isn't correct
6 Incorrect 541 ms 108508 KB Output isn't correct
7 Runtime error 54 ms 131072 KB Execution killed with signal 9
8 Runtime error 49 ms 131072 KB Execution killed with signal 9
9 Runtime error 51 ms 131072 KB Execution killed with signal 9
10 Runtime error 57 ms 131072 KB Execution killed with signal 9
11 Runtime error 50 ms 131072 KB Execution killed with signal 9
12 Runtime error 54 ms 131072 KB Execution killed with signal 9
13 Runtime error 48 ms 131072 KB Execution killed with signal 9
14 Runtime error 50 ms 131072 KB Execution killed with signal 9
15 Runtime error 55 ms 131072 KB Execution killed with signal 9
16 Runtime error 49 ms 131072 KB Execution killed with signal 9
17 Runtime error 51 ms 131072 KB Execution killed with signal 9