oj.uz

Submission #964886

# Submission time Handle Problem Language Result Execution time Memory
964886 2024-04-17T16:58:03 Z codefox Regions (IOI09_regions) C++14
55 / 100
 7672 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 = 120;
int N = 205000;

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

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

    dpback.assign(n, vector<int>(K, 0));
    backsolutions.assign(r, vector<int>(K, -1));

    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]>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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 556 KB Output is correct
5 Correct 5 ms 784 KB Output is correct
6 Correct 10 ms 1112 KB Output is correct
7 Correct 17 ms 1384 KB Output is correct
8 Correct 21 ms 1728 KB Output is correct
9 Correct 36 ms 4064 KB Output is correct
10 Correct 76 ms 6460 KB Output is correct
11 Correct 131 ms 9324 KB Output is correct
12 Correct 146 ms 12708 KB Output is correct
13 Correct 224 ms 14196 KB Output is correct
14 Correct 403 ms 17856 KB Output is correct
15 Correct 394 ms 27660 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1927 ms 45372 KB Output isn't correct
2 Incorrect 2145 ms 46116 KB Output isn't correct
3 Incorrect 3450 ms 55900 KB Output isn't correct
4 Correct 371 ms 20028 KB Output is correct
5 Correct 369 ms 26992 KB Output is correct
6 Correct 2279 ms 34612 KB Output is correct
7 Correct 2827 ms 46604 KB Output is correct
8 Correct 2511 ms 70392 KB Output is correct
9 Correct 3992 ms 97164 KB Output is correct
10 Correct 7672 ms 121240 KB Output is correct
11 Correct 6709 ms 127804 KB Output is correct
12 Incorrect 1730 ms 119472 KB Output isn't correct
13 Incorrect 2430 ms 120396 KB Output isn't correct
14 Incorrect 4803 ms 126936 KB Output isn't correct
15 Runtime error 104 ms 131072 KB Execution killed with signal 9
16 Runtime error 107 ms 131072 KB Execution killed with signal 9
17 Runtime error 98 ms 131072 KB Execution killed with signal 9