oj.uz

Submission #964826

# Submission time Handle Problem Language Result Execution time Memory
964826 2024-04-17T15:44:32 Z codefox Regions (IOI09_regions) C++14
25 / 100
 618 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 = 450;

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 2 ms 872 KB Output is correct
5 Correct 7 ms 1368 KB Output is correct
6 Correct 12 ms 2904 KB Output is correct
7 Correct 23 ms 3672 KB Output is correct
8 Correct 23 ms 4692 KB Output is correct
9 Correct 50 ms 11196 KB Output is correct
10 Correct 91 ms 20616 KB Output is correct
11 Correct 175 ms 29444 KB Output is correct
12 Correct 196 ms 39812 KB Output is correct
13 Correct 273 ms 46112 KB Output is correct
14 Correct 478 ms 57060 KB Output is correct
15 Correct 481 ms 79728 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 131072 KB Execution killed with signal 9
2 Runtime error 53 ms 131072 KB Execution killed with signal 9
3 Runtime error 51 ms 131072 KB Execution killed with signal 9
4 Correct 443 ms 70816 KB Output is correct
5 Correct 503 ms 89812 KB Output is correct
6 Incorrect 618 ms 122800 KB Output isn't correct
7 Runtime error 50 ms 131072 KB Execution killed with signal 9
8 Runtime error 50 ms 131072 KB Execution killed with signal 9
9 Runtime error 63 ms 131072 KB Execution killed with signal 9
10 Runtime error 49 ms 131072 KB Execution killed with signal 9
11 Runtime error 51 ms 131072 KB Execution killed with signal 9
12 Runtime error 51 ms 131072 KB Execution killed with signal 9
13 Runtime error 52 ms 131072 KB Execution killed with signal 9
14 Runtime error 53 ms 131072 KB Execution killed with signal 9
15 Runtime error 50 ms 131072 KB Execution killed with signal 9
16 Runtime error 53 ms 131072 KB Execution killed with signal 9
17 Runtime error 57 ms 131072 KB Execution killed with signal 9