oj.uz

Submission #964905

# Submission time Handle Problem Language Result Execution time Memory
964905 2024-04-17T17:11:14 Z codefox Regions (IOI09_regions) C++14
100 / 100
 7472 ms 129824 KB 
#include<bits/stdc++.h>

using namespace std;

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

#define pii pair<int, char>

const int K = 90;
const int N = 200000;
const int R = 25000;

vector<int> graph[N];
short region[N];
vector<int> rind;

int start[N];
int ende[N];
int c =0 ;

vector<vector<int>> dpback;

int backsolutions[R][K];
int frontsolutions[K][R];

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);
    }
    dpfront.clear();
}

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;

    rind.assign(r, -1);

    for (int i = 0; i < R*K; i++)
    {
        backsolutions[0][i] = 0;
        frontsolutions[0][i] = 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]*K > N) 
        {
            rind[i] = d++;
        }
    }
    rsum.clear();

    dpback.assign(n, vector<int>(K, 0));

    dfsback(0);
    dpback.clear();
    dfsfront(0, vector<int>(K, 0));

    vector<pii> s;
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (rind[a]!=-1) cout << frontsolutions[rind[a]][b] << endl;
        else if (rind[b]!=-1) cout << backsolutions[a][rind[b]] << endl;
        else
        {
            for (int ele:part[a]) 
            {
                s.push_back({start[ele], 2});
                s.push_back({ende[ele], 0});
            }
            for (int ele:part[b])
            {
                s.push_back({start[ele], 1});
            }
            sort(s.begin(), s.end());

            int open = 0;
            int sol = 0;
            for (pii ele:s)
            {
                if (ele.second == 0) open--;
                if (ele.second == 1) sol += open;
                if (ele.second == 2) open++;
            }
            cout << sol << endl;
            s.clear();
        }
    }

    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:76:29: warning: iteration 90 invokes undefined behavior [-Waggressive-loop-optimizations]
   76 |         backsolutions[0][i] = 0;
      |         ~~~~~~~~~~~~~~~~~~~~^~~
regions.cpp:74:23: note: within this loop
   74 |     for (int i = 0; i < R*K; i++)
      |                     ~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24664 KB Output is correct
2 Correct 4 ms 24664 KB Output is correct
3 Correct 5 ms 24664 KB Output is correct
4 Correct 7 ms 24772 KB Output is correct
5 Correct 10 ms 24920 KB Output is correct
6 Correct 14 ms 25176 KB Output is correct
7 Correct 28 ms 25176 KB Output is correct
8 Correct 24 ms 25432 KB Output is correct
9 Correct 40 ms 27348 KB Output is correct
10 Correct 65 ms 28792 KB Output is correct
11 Correct 145 ms 30956 KB Output is correct
12 Correct 151 ms 33368 KB Output is correct
13 Correct 221 ms 34248 KB Output is correct
14 Correct 403 ms 37272 KB Output is correct
15 Correct 402 ms 46568 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1902 ms 57416 KB Output is correct
2 Correct 2085 ms 57488 KB Output is correct
3 Correct 3563 ms 65772 KB Output is correct
4 Correct 349 ms 37500 KB Output is correct
5 Correct 403 ms 42860 KB Output is correct
6 Correct 2237 ms 46872 KB Output is correct
7 Correct 2808 ms 54660 KB Output is correct
8 Correct 2510 ms 73520 KB Output is correct
9 Correct 3864 ms 89908 KB Output is correct
10 Correct 7472 ms 105688 KB Output is correct
11 Correct 6425 ms 107544 KB Output is correct
12 Correct 1669 ms 105408 KB Output is correct
13 Correct 2368 ms 106176 KB Output is correct
14 Correct 4791 ms 109312 KB Output is correct
15 Correct 4437 ms 116524 KB Output is correct
16 Correct 3634 ms 129824 KB Output is correct
17 Correct 4581 ms 125148 KB Output is correct