oj.uz

Submission #964833

# Submission time Handle Problem Language Result Execution time Memory
964833 2024-04-17T15:54:42 Z codefox Regions (IOI09_regions) C++14
48 / 100
 7371 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 = 100;

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);
    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)/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)/K) cout << frontsolutions[rind[a]][b] << endl;
        else if (rsum[b]>(n+K)/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
8.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 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 344 KB Output isn't correct
5 Incorrect 4 ms 600 KB Output isn't correct
6 Incorrect 13 ms 1112 KB Output isn't correct
7 Incorrect 21 ms 1108 KB Output isn't correct
8 Correct 23 ms 1640 KB Output is correct
9 Correct 38 ms 3928 KB Output is correct
10 Correct 80 ms 5800 KB Output is correct
11 Correct 147 ms 8240 KB Output is correct
12 Correct 150 ms 11284 KB Output is correct
13 Correct 232 ms 12448 KB Output is correct
14 Correct 427 ms 15572 KB Output is correct
15 Correct 417 ms 24672 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2009 ms 39424 KB Output isn't correct
2 Incorrect 1761 ms 39932 KB Output isn't correct
3 Incorrect 3580 ms 48948 KB Output isn't correct
4 Correct 358 ms 18988 KB Output is correct
5 Correct 413 ms 25664 KB Output is correct
6 Correct 2355 ms 32736 KB Output is correct
7 Correct 2949 ms 44248 KB Output is correct
8 Correct 2608 ms 65624 KB Output is correct
9 Correct 3863 ms 90124 KB Output is correct
10 Correct 7371 ms 115756 KB Output is correct
11 Correct 6397 ms 119980 KB Output is correct
12 Incorrect 1680 ms 109600 KB Output isn't correct
13 Incorrect 2317 ms 110532 KB Output isn't correct
14 Incorrect 4639 ms 117548 KB Output isn't correct
15 Incorrect 4600 ms 129072 KB Output isn't correct
16 Runtime error 242 ms 131072 KB Execution killed with signal 9
17 Runtime error 282 ms 131072 KB Execution killed with signal 9