oj.uz

Submission #964904

# Submission time Handle Problem Language Result Execution time Memory
964904 2024-04-17T17:09:02 Z codefox Regions (IOI09_regions) C++14
90 / 100
 7399 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>

const int K = 100;
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);
    }
}

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:75:29: warning: iteration 100 invokes undefined behavior [-Waggressive-loop-optimizations]
   75 |         backsolutions[0][i] = 0;
      |         ~~~~~~~~~~~~~~~~~~~~^~~
regions.cpp:73:23: note: within this loop
   73 |     for (int i = 0; i < R*K; i++)
      |                     ~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26456 KB Output is correct
2 Correct 5 ms 26456 KB Output is correct
3 Correct 6 ms 26456 KB Output is correct
4 Correct 8 ms 26712 KB Output is correct
5 Correct 8 ms 26712 KB Output is correct
6 Correct 15 ms 27032 KB Output is correct
7 Correct 20 ms 27224 KB Output is correct
8 Correct 28 ms 27528 KB Output is correct
9 Correct 42 ms 29416 KB Output is correct
10 Correct 75 ms 31236 KB Output is correct
11 Correct 136 ms 33576 KB Output is correct
12 Correct 152 ms 36272 KB Output is correct
13 Correct 220 ms 37548 KB Output is correct
14 Correct 423 ms 40644 KB Output is correct
15 Correct 419 ms 50268 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2004 ms 62980 KB Output is correct
2 Correct 2258 ms 63308 KB Output is correct
3 Correct 3679 ms 70792 KB Output is correct
4 Correct 397 ms 40744 KB Output is correct
5 Correct 390 ms 46384 KB Output is correct
6 Correct 2394 ms 49956 KB Output is correct
7 Correct 2994 ms 59908 KB Output is correct
8 Correct 2627 ms 80100 KB Output is correct
9 Correct 3846 ms 98800 KB Output is correct
10 Correct 7399 ms 115752 KB Output is correct
11 Correct 6447 ms 119004 KB Output is correct
12 Correct 1663 ms 116344 KB Output is correct
13 Correct 2333 ms 117276 KB Output is correct
14 Correct 4643 ms 120432 KB Output is correct
15 Correct 4396 ms 127872 KB Output is correct
16 Runtime error 87 ms 131072 KB Execution killed with signal 9
17 Runtime error 93 ms 131072 KB Execution killed with signal 9