oj.uz

Submission #964866

# Submission time Handle Problem Language Result Execution time Memory
964866 2024-04-17T16:46:48 Z codefox Regions (IOI09_regions) C++14
55 / 100
 7656 ms 131072 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#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 = 80;
int N = 201000;

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;
            ll 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 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 344 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 11 ms 1112 KB Output is correct
7 Correct 19 ms 1108 KB Output is correct
8 Correct 18 ms 1368 KB Output is correct
9 Correct 30 ms 3420 KB Output is correct
10 Correct 64 ms 4972 KB Output is correct
11 Correct 123 ms 7008 KB Output is correct
12 Correct 130 ms 9648 KB Output is correct
13 Correct 201 ms 10492 KB Output is correct
14 Correct 409 ms 13188 KB Output is correct
15 Correct 396 ms 21464 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1921 ms 33532 KB Output isn't correct
2 Incorrect 2119 ms 33628 KB Output isn't correct
3 Incorrect 3621 ms 41852 KB Output isn't correct
4 Correct 338 ms 15960 KB Output is correct
5 Correct 394 ms 21980 KB Output is correct
6 Correct 2301 ms 27560 KB Output is correct
7 Correct 2909 ms 37204 KB Output is correct
8 Correct 2576 ms 56224 KB Output is correct
9 Correct 3998 ms 76036 KB Output is correct
10 Correct 7656 ms 98528 KB Output is correct
11 Correct 6531 ms 100408 KB Output is correct
12 Incorrect 1655 ms 92224 KB Output isn't correct
13 Incorrect 2379 ms 93164 KB Output isn't correct
14 Incorrect 4728 ms 98752 KB Output isn't correct
15 Incorrect 4387 ms 109288 KB Output isn't correct
16 Runtime error 254 ms 131072 KB Execution killed with signal 9
17 Incorrect 4725 ms 115652 KB Output isn't correct