oj.uz

Submission #964837

# Submission time Handle Problem Language Result Execution time Memory
964837 2024-04-17T16:01:36 Z codefox Regions (IOI09_regions) C++14
13 / 100
 3714 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

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

#define ll long long
#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<ll>> backsolutions;
vector<vector<ll>> frontsolutions;

int K = 200;

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<ll>(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, 0);
    int d =0;
    for (int i = 0; i < n; i++) rsum[region[i]]++;
    for (int i = 0; i < r; i++)
    {
        if (rsum[i]> n/K) 
        {
            rind[i] = d++;
        }
    }

    rsum.resize(0);
    dfsback(0);
    dpback.resize(0);
    frontsolutions.assign(K, vector<ll>(r, -1));
    dfsfront(0, vector<int>(K, 0));

    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (rsum[a]>n/K) cout << frontsolutions[rind[a]][b] << endl;
        else if (rsum[b]>n/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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Incorrect 2 ms 600 KB Output isn't correct
5 Incorrect 4 ms 856 KB Output isn't correct
6 Incorrect 13 ms 1880 KB Output isn't correct
7 Incorrect 16 ms 1880 KB Output isn't correct
8 Incorrect 18 ms 2392 KB Output isn't correct
9 Incorrect 43 ms 6232 KB Output isn't correct
10 Correct 84 ms 10056 KB Output is correct
11 Incorrect 153 ms 14312 KB Output isn't correct
12 Correct 180 ms 19472 KB Output is correct
13 Correct 239 ms 22080 KB Output is correct
14 Incorrect 207 ms 27472 KB Output isn't correct
15 Incorrect 464 ms 40712 KB Output isn't correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1529 ms 68932 KB Output isn't correct
2 Incorrect 1686 ms 71412 KB Output isn't correct
3 Incorrect 3714 ms 84368 KB Output isn't correct
4 Incorrect 281 ms 33808 KB Output isn't correct
5 Correct 440 ms 44056 KB Output is correct
6 Incorrect 438 ms 58572 KB Output isn't correct
7 Incorrect 1350 ms 79480 KB Output isn't correct
8 Correct 2844 ms 112584 KB Output is correct
9 Runtime error 53 ms 131072 KB Execution killed with signal 9
10 Runtime error 50 ms 131072 KB Execution killed with signal 9
11 Runtime error 50 ms 131072 KB Execution killed with signal 9
12 Runtime error 50 ms 131072 KB Execution killed with signal 9
13 Runtime error 59 ms 131072 KB Execution killed with signal 9
14 Runtime error 50 ms 131072 KB Execution killed with signal 9
15 Runtime error 58 ms 131072 KB Execution killed with signal 9
16 Runtime error 51 ms 131072 KB Execution killed with signal 9
17 Runtime error 50 ms 131072 KB Execution killed with signal 9